TR14-017 Authors: Eli Ben-Sasson, Emanuele Viola

Publication: 9th February 2014 20:33

Downloads: 2009

Keywords:

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

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)}$.