Combinatorics Seminar
When: Sunday, November 23, 10am
Where: Schreiber 309
Speaker: Ido Ben-Eliezer, Tel Aviv University
Title: Random polynomials are almost balanced: Proof and
applications
Abstract:
Given a multivariate polynomial p, the bias of p is
|\Pr[p(x)=1]-\Pr[p(x)=0]|.
We prove that for large enough n, and d at most cn for some constant c, the bias
of a randomly chosen polynomial on n variables of degree d is very small
with high probability, thus getting a bound on the weight distribution
of Reed-Muller codes.
We also provide two applications of this claim. First, we provide a
nearly tight lower bound on the size of distributions that fool low
degree polynomials. Second, we prove that a typical low degree polynomial
cannot be approximated by polynomials of lower degree.
Based on a joint work with Noga Alon and Michael Krivelevich and a
joint work with Rani Hod and Shachar Lovett.