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

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

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

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