City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Анализ Фурье и изучение булевых функций в PAC-модели
Boolean function analysis

What: Lecture
When: Saturday, 20 April 2019, 17:15–20:30
Where: ПОМИ РАН

Description

В это лекции мы обсудим вопросы анализа Фурье, близкие к теории сложности вычислений. Для этого мы изучим поведение коэффициентов Фурье при простейших преобразованиях булевых функций, а именно при подстановке констант и сужении на подпространства. В качестве приложения мы обсудим какие результаты можно получать с помощью анализа Фурье для модели разрешающих деревьев. Также мы рассмотрим приложения анализа к изучению булевых функций в PAC-модели. Мы обсудим, что если спектр Фурье функции сосредоточен на известном небольшом множестве, то функцию можно эффективно изучить в PAC-модели со случайными примерами. Затем мы обсудим, что если спектр Фурье функции сосредоточен на неизвестном небольшом множестве, то функцию можно эффективно изучить в PAC-модели с запросами.

Video