On approximation of Boolean functions by small degree real polynomials

Problems of approximating Boolean functions by real polynomials have numerous applications in complexity theory and machine learning. In this talk we consider the following universal setting generalizing many other models: what is the maximal fraction of points in the Boolean cube on which a given Boolean function may coincide with real polynomials of a given degree? Our main result states that the answer is exactly 1/2 for the parity function and polynomials of degree (1/2)log log n. The main ingredient of our proof is a combinatorial version of a celebrated anticoncentration result by Costello, Tao and Vu that is apparently of independent interest.
Joint work with E. Viola (Northeastern University).