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

• 18.408 F2022 Lectures 4–6: Quadratic Solvability, Low-degree Extensions and the Sum-check Protocolocw.mit.edu
• A Mathematical Theory of Communicationpeople.math.harvard.edu
• [2605.01192] Linear-Readout Floors and Threshold Recovery in Computation in Superpositionarxiv.org
• Visual Information Theory -- colah's blogcolah.github.io
• 0602157.pdfarxiv.org
• Forbidding Exactly One Hamming Distancearxiv.org
• But what are Hamming codes? The origin of error correctionyoutube.com
• Reed–Solomon error correction - Wikipediaen.wikipedia.org
• [2608.00140] Discrepancy Theory: An Algorithmic and Geometric Perspectivearxiv.org
• notes.pdfcourses.maths.ox.ac.uk
• A Brief Introduction to Fourier Analysis on the Boolean Cubetheoryofcomputing.org
• unit-distance-cot.pdfcdn.openai.com