Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROXIMITY TESTING:
Reports tagged with proximity testing:
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 >>>

TR20-165 | 6th November 2020
In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(D)$. The problem of testing proximity to an ... more >>>