Structure and Pseudo-Randomness in Coding Theory

Friday, March 20, 2015 - 10:20am - 11:00am
Klaus 1116
Shachar Lovett (University of California, San Diego)
The theory of structure and pseudo-randomness has been very influential in several areas of mathematics, such as number theory, graph theory and Fourier analysis. It is also very influential in several areas of theoretical computer science, such as complexity theory, cryptography and property testing. In a high level, it allows to analyse arbitrary objects by decomposing them to a structural component and a pseudo-random component. The pseudo-random component behaves in many senses like random noise, while the structural component has a concise representation which makes it amenable to analysis and algorithmic manipulation.

In this talk, I will describe applications of this paradigm to coding theory. I will describe a new general approach to list decoding, which follows by decomposing an arbitrary received word to a structural received word and pseudo-random noise. This allows for a simplified analysis of the list decoding problem. In particular, I will describe how this approach leads to a resolution of a conjecture by Gopalan, Klivans, and Zuckerman, that the list decoding radius of Reed-Muller codes (in certain regimes) is equal to the minimal distance of the code.

Based on joint works with Abhishek Bhowmick.