Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity

The PCP theorem [Arora et al. 1998; Arora and Safra 1998] 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, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length n by PCPs of length n.poly log 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(epsilon), 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).