Computer Science/Discrete Mathematics Seminar II

A Locally Decodable Codes (LDC) is an error correcting code which allows the decoding of a single message symbol from a few queries to a possibly corrupted encoding.  LDCs can be constructed, for example, from low degree polynomials over a finite field (with local decoding along a random line) and also using set systems  with restricted modular  intersections (Matching-Vector codes). Despite the wide range of applications in mathematics and theoretical computer science, there are still big gaps in our understanding of LDCs. In particular, we still don't know if there exist LDCs with polynomial  encoding length and constant locallity (even non-explicitly).  In this talk I will survey the known lower and upper bounds on LDCs and outline the main open problems. We will focus on the linear algebraic (as opposed to information theoretic) view of LDCs, allowing for an arbitrary underlying field. This view leads to problem statements which are reminiscent of  more traditional line/point incidence problems.