Keywords: coding theory, decoding, polynomials
Prerequisites: 01018: Discrete Mathematics 2, (01405: Algebraic Coding Theory)
Locally decodable codes are a type of error-correcting code for encoding and storing information in a reliable way and such that you can “locally” get the information back: you can retrieve just a single symbol of the original information at a time by looking at only very few symbols of the encoded data, and those symbols can be chosen basically randomly! Even more, we still have error-correction so even if some of the retrieved symbols were wrong, we still correctly obtain the information symbol we were looking for.
These codes are useful for privacy services in distributed storage, and have also had a huge theoretical impact in proof theory as enablers of probabilistically checkable proofs.
The constructions are algebraic and rely on evaluation and interpolation of multivariate polynomials over finite fields. The proofs that they exhibit “random” local reconstruction draw on algebraic geometry.
The project could be purely theoretic, by studying the basic constructions and more recent proposals in research papers, or it can be made more practical by implementing one or more of the schemes.