City: Санкт-Петербург Новосибирск Казань Language: Русский English

Основные определения анализа Фурье, приложения к тестированию свойств
Анализ булевых функций


What: Lecture
When: Friday, 19 April 2019, 18:00–20:50
Where: ПОМИ РАН

Description

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

Video