

Seminar of the Department of Mathematical Logic "Algorithmic problems in algebra and logic"
December 11, 2012 18:30–20:05, Moscow, MSU, auditorium 1604






On approximation of Boolean functions by small degree real polynomials
A. A. Razborov^{} 
Number of views: 
This page:  134 

Abstract:
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).
Website:
http://eccc.hpiweb.de/report/2012/134

