Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-017 | 9th February 2014 20:33

Short PCPs with projection queries


Authors: Eli Ben-Sasson, Emanuele Viola
Publication: 9th February 2014 20:33
Downloads: 2621


We construct a PCP for NTIME(2$^n$) with constant
soundness, $2^n \poly(n)$ proof length, and $\poly(n)$
queries where the verifier's computation is simple: the
queries are a projection of the input randomness, and the
computation on the prover's answers is a 3CNF. The
previous upper bound for these two computations was
polynomial-size circuits. Composing this verifier with a
proof oracle increases the circuit-depth of the latter by
$2$. Our PCP is a simple variant of the PCP by
Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (CCC
2005). We also give a more modular exposition of the
latter, separating the combinatorial from the algebraic

If our PCP is taken as a black box, we obtain a more
direct proof of the result by Williams, later with
Santhanam (CCC 2013) that derandomizing circuits on $n$
bits from a class $C$ in time $2^n/n^{\omega(1)}$ yields
that NEXP is not in a related circuit class $C'$. Our
proof yields a tighter connection: $C$ is an And-Or of
circuits from $C'$. Along the way we show that the same
lower bound follows if the satisfiability of the And of
any 3 circuits from $C'$ can be solved in time

ISSN 1433-8092 | Imprint