Lower bounds for Locally Correctable Codes over fields of characteristic zero

Project Description

Error correcting codes are ubiquitous in computer science, both in theory and in practice. In recent years there has been growing interest in constructing error correcting codes which have local properties, as these codes can be used to safely store large amounts of data, while enabling users to efficiently recover small amounts of data without querying the entire codeword. Despite much progress made in the construction of error correcting codes with high rate and distance, many challenges still remain on whether such powerful codes exist with the additional local properties mentioned above.

The goal of this project is to prove that error correcting codes which have the ability of being locally corrected cannot have high rate and distance, when the base field is of characteristic zero.

Background Reading

Some useful references for this project are:

• Yekhanin’s survey on locally decodable codes
• Madhu Sudan’s coding theory lecture notes in particular the lectures concerning locally decodable and correctable codes
• Zeev Dvir’s lecture notes on locally decodable/correctable codes
• Recent paper on locally correctable codes

Prerequisites

The ideal URA should have a solid command of:

• linear algebra (equivalent of MATH 245, or MATH 235),
• basic abstract algebra (such as the material from PMATH 347),
• coding theory
• quantum information theory (not required, but a plus)
• experience with writing rigorous proofs

Note: some of the prerequisites can be waived if the student has excellent academic background, such as international olympiads experience, or other similar achievements.

Applying

If you are interested and have the prerequisites for this project, please send me the following by email:

• Transcript
• Resume
• 1-2 paragraphs on why you are interested in this project (in particular, you should understand at least what a locally correctable/decodable code is)

Note: any applications deviating significantly from the above instructions will be ignored.