Computer Science/Discrete Mathematics Seminar I

Locally decodable codes (LDCs) are error-correcting codes that allow for highly-efficient recovery of "pieces" of information even after arbitrary corruption of a codeword. Locally testable codes (LTCs) are those that allow for highly-efficient testing to see if some given word is close to a codeword. Codes derived from evaluations of low-degree multivariate polynomials give the simplest example of LDCs and LTCs, and these codes and their locality properties played a significant role in many results in complexity theory in the 90s. Attempts to construct better LTCs and LDCs (those that offer better coding efficiency, while achieving a desired level of locality) have been quite successful in the past decade. However the constructions often tend to be complex and have inevitably led to codes which satisfy one of the two properties, but not both! In this talk we will show how small codes can be lifted to longer ones retaining the locality of the small ones, while achieving high rate. In particular we give codes of rate close to arbitrarily one with locality $n^\epsilon$ for arbitrary $\epsilon > 0$. The only previous LDCs with such properties are the multiplicity codes of Kopparty, Saraf, and Yekhanin. Our codes are naturally LTCs also, whereas this aspect remains open for the multiplicity codes. We will use these codes as an excuse to give an overview of some of the work in "affine-invariant codes" - of which lifted codes are a subclass. The testability and rate of our lifted codes follows from some of the analysis of the general class. One surprising fact that leads to our high-rate codes is that the set of multivariate functions that project to a univariate polynomial of degree d on every line, is *not* the set of degree d multivariate polynomials, but an overwhelmingly larger set over fields of small characteristic. This fact turns out to lead to some strong lower bounds on the size of "Nikodym sets" (sets that contain "most points of at least one line" through every point in the space). Joint work with Alan Guo (MIT) and Swastik Kopparty (Rutgers)