18.408 F2022 Lectures 2–3: Error Correcting Codes

N/A

18.408 Topics in Theoretical Computer Science Fall 2022 Lectures 2 and 3 Dor Minzer The topic for today is error correcting codes, which can be thought of as combinatorial analogs of PCPs. We will give some basic definitions and examples of error correcting codes, as well as discuss notions such as local testability and concatenation/ composition of error correcting codes. In particular, we will show how to construct an explicit error correcting code with constant rate, relative distance and binary…

related reading

• book.pdfinference.org.uk
• Reed–Solomon error correction - Wikipediaen.wikipedia.org
• A Mathematical Theory of Communicationpeople.math.harvard.edu
• Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errorsarxiv.org
• WHIR: Reed–Solomon Proximity Testing with Super-Fast Verificationeprint.iacr.org
• 0602157.pdfarxiv.org
• [1907.11157] Quantum Error Correction: An Introductory Guidearxiv.org
• [2605.01192] Linear-Readout Floors and Threshold Recovery in Computation in Superpositionarxiv.org
• arXiv:quant-ph/0207170v1 30 Jul 2002arxiv.org
• [2601.20927] Entangling logical qubits without physical operationsarxiv.org
• Sending Samples Without Bits-Backjoschu.net
• ProofsArgsAndZK.pdfpeople.cs.georgetown.edu