Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in ... more >>>