Tata Institute of Fundamental Research
Low Degree Local Correction Over the Boolean Cube
STCS Seminar
Speaker:
Prashanth Amireddy (Harvard John A. Paulson School of Engineering and Applied Sciences)
Organiser:
Prahladh Harsha, Raghuvansh Saxena
Date:
Tuesday, 24 Dec 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Reed-Muller codes are an important class of error-correcting codes based on evaluating low-degree polynomials over a vector space. In this talk, I will discuss our recent results about a variant of Reed-Muller codes obtained by considering low-degree "group-polynomials", which are functions mapping {0,1}^n to an Abelian group G. Such functions naturally arise in Boolean circuit complexity and learning theory, and this work furthers the study of their coding-theoretic properties.
We will discuss our results showing that degree-d group-polynomials are locally correctable with nearly O(log n)^d queries, for the fraction of errors approaching half the minimum distance of the code. Key to this is constructing a novel "interpolating set" for degree-d polynomials, that lies between two exponentially close parallel hyperplanes.
Finally, I will sketch some of the techniques used to demonstrate the list-decodability (in fact, local list-correctability as well) of these codes for error rates approaching their minimum distance. This relies on combining results about the anti-concentration of low-degree polynomials, the sunflower lemma, and the footprint bound for counting common zeros of polynomials.
This is joint work with Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan and Madhu Sudan.
Short Bio: Prashanth is a third-year PhD student at Harvard co-advised by Professors Madhu Sudan and Salil Vadhan. He is interested in theoretical computer science, specifically in coding theory, pseudorandomness and complexity theory. Outside of research, he likes to run, bike and jump.
| Speaker: | Prashanth Amireddy (Harvard John A. Paulson School of Engineering and Applied Sciences) |
| Organiser: | Prahladh Harsha, Raghuvansh Saxena |
| Date: | Tuesday, 24 Dec 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
We will discuss our results showing that degree-d group-polynomials are locally correctable with nearly O(log n)^d queries, for the fraction of errors approaching half the minimum distance of the code. Key to this is constructing a novel "interpolating set" for degree-d polynomials, that lies between two exponentially close parallel hyperplanes.
Finally, I will sketch some of the techniques used to demonstrate the list-decodability (in fact, local list-correctability as well) of these codes for error rates approaching their minimum distance. This relies on combining results about the anti-concentration of low-degree polynomials, the sunflower lemma, and the footprint bound for counting common zeros of polynomials.
This is joint work with Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan and Madhu Sudan.