Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Daniel Augot:

TR21-118 | 11th August 2021
Daniel Augot, Sarah Bordage, Jade Nardi

Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an
oracle function $f : L^m \rightarrow \mathbb F_q$, where $L\subset \mathbb F_q$, a verifier distinguishes whether $f$ is the evaluation of a ... more >>>

ISSN 1433-8092 | Imprint