RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Search
RSS
Forthcoming seminars





You may need the following programs to see the files








Seminar of the Department of Mathematical Logic "Algorithmic problems in algebra and logic"
December 11, 2012 18:30, Moscow, MSU, auditorium 16-04
 


On approximation of Boolean functions by small degree real polynomials

A. A. Razborov

Number of views:
This page:120

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.hpi-web.de/report/2012/134

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017