Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOW DEGREE TESTING:
Reports tagged with Low degree testing:
TR97-003 | 29th January 1997
Sanjeev Arora, Madhu Sudan

Improved low-degree testing and its applications


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 >>>


TR18-090 | 4th May 2018
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Worst-case to average case reductions for the distance to a code

Revisions: 1

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 >>>


TR19-044 | 28th March 2019
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2

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 >>>




ISSN 1433-8092 | Imprint