Local correction is an algorithmic task where given query access to a corrupted codeword, the goal is to efficiently recover a specific entry of the closest codeword. In this talk, we will consider local correction for (evaluation of) low- degree polynomials. More specifically, we will consider evaluation of low-degree polynomials over the Boolean cube (and grids) and the coefficients will be from arbitrary field (i.e., they can be reals too).
We will see sublinear query algorithms for local correction and also local list correction of low-degree polynomials over grids. We will see a natural application of it for hardness amplification of counting problems. We will also see a couple of nice combinatorial ideas/results that go into designing these algorithms. One such example is a version of polynomial distance lemma (widely known as the Schwartz-Zippel Lemma) over Boolean hamming slices.
This talk will be based on a series of joint work with Prashanth Amireddy, Manaswi Paraashar, Srikanth Srinivasan, and Madhu Sudan.
