Title: Local Correction of Linear Functions over the Boolean Cube
Speaker: Madhu Sudan
Affiliation: Harvard John A. Paulson School of Engineering and Applied Sciences

Abstract:

Since the late 1980's it has been known that low-degree multivariate polynomials over finite fields form "locally correctible codes". In other words, given oracle access to a function f:F^n -> F such there is a degree d polynomial P(X1...Xn) whose evaluation agree with f on all but a tiny fraction of points, and an arbitrary point b in F^n, it is 
possible to determine P(b) with high probability while querying f in a constant number of points (where the number of queries depends on the degree d, but not the number of variables n).

Of course this result doesn't work for infinite fields since then one has to define a measure over F^n. But can one hope for a similar result for f:S^n \to F for some finite subset S of F? In a previous work with Bafna and Srinivasan we had shown that any such local decoding result (over say the reals or rationals) would require roughly Omega-tilde(\log n) queries (even when d = 1).

In this talk we describe a complementary result that shows that O-tilde(\log n) queries suffice in the linear (d=1) case when S = {0,1} (over any field F, and indeed any abelian group G). Working over sets like S^n provides novel challenges due to the fact that the most handy tool in previous works, namely affine-invariance of the domain, is no longer available. Our local reconstruction algorithms rely centrally on the ability to construct a small set of nearly balanced vectors in {-1,1}^n whose span contains 1^n. Combined with a double dose of hypercontractivity this leads to a local algorithm correcting up to 1/4  fraction of errors. Our final result gives a list-decoding algorithm correcting nearly 50% errors. Here the key ingredient is the combinatorial bound on the list size which we prove using a kitchen sink of techniques that show large lists must contain many sparse polynomials and then ruling out such possibilities which involves case analysis depending on the group G.

Joint work with Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, and Srikanth Srinivasan.