Under the auspices of the Computational Complexity Foundation (CCF)

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

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