Computer Science/Discrete Mathematics Seminar II

A locally correctable code (LCC) is an error-correcting code where one can recover any symbol of the original codeword by querying only a small number of randomly chosen symbols from the received corrupted codeword. In recent years, there has been substantial progress on understanding locally correctable codes via connections to extremal combinatorics. Such connections typically rely on extremal combinatorics results that show the existence of cycles with a certain restricted color palette, e.g,. a rainbow cycle, in edge-colored graphs. In this talk, we will discuss these recent developments and show some new results.

Based primarily on joint work with Oliver Janzer.