ECCC-Report TR14-017https://eccc.weizmann.ac.il/report/2014/017Comments and Revisions published for TR14-017en-usSun, 09 Feb 2014 20:33:52 +0200
Paper TR14-017
| Short PCPs with projection queries |
Eli Ben-Sasson,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2014/017We 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
arguments.
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
$2^n/n^{\omega(1)}$.Sun, 09 Feb 2014 20:33:52 +0200https://eccc.weizmann.ac.il/report/2014/017