|
|
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
December 11, 2012 18:30–20:05, Moscow, Steklov Mathematical Institute
|
|
|
|
|
|
On approximation of Boolean functions by small degree real polynomials
A. A. Razborov |
Number of views: |
This page: | 370 |
|
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
|
|