Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with algebraic geometry codes:
TR12-148 | 7th November 2012
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

TR13-085 | 13th June 2013
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

Constant rate PCPs for circuit-SAT with sublinear query complexity

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

TR20-165 | 6th November 2020
Sarah Bordage, Jade Nardi

Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Revisions: 2

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

ISSN 1433-8092 | Imprint