Can PCPs (or just LTCs) of constant query complexity have constant rate? The known constructions incure a polylogarithmic factor, where in the case of PCPs one log factor seems to arize from the simulation of an arbitrary compution on a fixed network and another from the underlying codes. The current work shows that both log factors can be eliminated if one allows a query complexity that is a small constant power of the length (i.e., query complexity $n^\eps$). In this case routing on a fixed network of such degree $d=n^\eps$ incurs only a constant overhead (of $\log_d n$), and adequate codes can be constructed (alas they are far more complex than the analogous LTCs (i.e., LTCs of the same parameters)).
The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, i.e., how long is the PCP compared to the original NP-proof. The state-of-the-art work of Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)) shows that one can encode proofs of length n by PCPs of length $n polylog n$ that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n, then one can construct PCPs of length O(n) for circuit-SAT, and PCPs of length O(t log t) for any language in NTIME(t).
More specifically, for any $epsilon>0$ we present (non-uniform) probabilistically checkable proofs (PCPs) of length $\exp(1/epsilon) n$ that can be checked using nqueries for circuit-SAT instances of size n. Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity (o(n)).
Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations which are crucial in earlier high-rate algebraic PCP constructions. Using this observation we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this paper for the first time for every message length, after they have been constructed for infinitely many message lengths by Stichtenoth [Trans. Information Theory 2006].
See ECCC TR13-085