|
|
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
11 декабря 2012 г. 18:30–20:05, г. Москва, Математический институт им.В.А.Стеклова РАН
|
|
|
|
|
|
О приближении булевых функций вещественными полиномами малой степени
А. А. Разборов |
Количество просмотров: |
Эта страница: | 370 |
|
Аннотация:
Задачи приближённого представления булевых функций вещественными полиномами имеют многочисленные приложения в теории сложности вычисления и теории машинного обучения. В настоящем докладе мы рассматриваем следующую универсальную постановку, обобщающую многие известные модели: какова максимально возможная доля точек булева куба, на которых данная булева функция может точно согласовываться с вещественными полиномами данной степени? Основной результат состоит в том, что для функции сложения по модулю 2 и полиномов степени (1/2)log log n ответ в точности равен 1/2. Ядром нашего доказательства служит комбинаторный вариант известной теоремы Costello-Tao-Vu о значительном отклонении, который, по-видимому, представляет независимый интерес.
Совместная работа с E. Viola (Northeastern University).
Website:
https://eccc.hpi-web.de/report/2012/134
|
|