Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Algebraic coding theory:
TR14-067 | 4th May 2014
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

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