Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>