|
SEMINARS |
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
|
|||
|
On approximation of Boolean functions by small degree real polynomials A. A. Razborov |
|||
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: https://eccc.hpi-web.de/report/2012/134 |