Семинар по сложности булевых функций

Общая информация
ЛекторА. С. Куликов
Семестросень 2011
Дата начала18.09.2011
Количество пар12
Язык курсарусский
Аннотация

Семинар посвящен одному из самых известных и сложных направлений theoretical computer science — схемной сложности булевых функций. Схема является очень естественной моделью вычисления булевых функций. Из мощностных соображений легко следует, что для почти любой булевой функции $ f \colon \{0,1\}^n \rightarrow \{0,1\} $ размер минимальной вычисляющей её схемы экспоненциален. Несмотря на это, до сих пор не известно ни одной явно заданной функции, требующей схем более чем линейного размера. По этой причине интенсивно изучаются ограниченные модели вычислений (такие как монотонные схемы, схемы ограниченной глубины, формулы, ветвящиеся программы). На семинаре будут рассмотрены различные методы доказательства нижних оценок для таких моделей. Семинар будет основан на новой книге Стасиса Юкны "Boolean Function Complexity: Advances and Frontiers".

Заинтересованным студентам будут выданы темы для доклада на семинаре. Подготовка к докладу подразумевает тщательное изучение выданной темы и подготовку слайдов. В конце семинара будет проведён экзамен.

Курсы по схемной сложности (с lecture notes!)

Дополнительная литература

Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение (А. Куликов)
(25.09.2011 - 13:00 - 14:35)

Булевы функции, симметрические булевы функции. Схемы и формулы. Доказательство оценки $ \Theta(2^n/n) $ на схемную сложность почти всех булевых функций от $ n $ переменных. Лучшие текущие нижние оценки для схем и формул.
2. Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов (А. Куликов)
(02.10.2011 - 11:15 - 12:50)

Основная идея метода элиминации гейтов. Примеры свойств функций, использующихся в доказательстве верхних оценок: $ 2n $ для функций, имеющих хотя бы три различные подфункции относительно любых двух переменных; $ 2n $ для функции индексации; $ 7n/3 $ для функций высокой степени.
3. Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов, продолжение (А. Куликов)
(02.10.2011 - 13:00 - 14:35)

$ 2.5n $ для симметрических функций, $ 3n $ для обобщённой функции индексации, $ 3n $ для аффинных дисперсеров.
4. Связь нижних оценок на графовую сложность с задачей P vs NP (И. Михайлин)
(23.10.2011 - 13:00 - 14:35)

Связь между графами и схемами, различные способы представить граф схемой: показательная и характеристическая схемы. P$ \neq $NP как следствие нижней оценки $ (12+\varepsilon)n $ на графовую сложность.
5. Нижние оценки для формул (И. Близнец)
(30.10.2011 - 13:00 - 14:35)

Связь глубины и размера формулы: $ D(f) = \Theta (\log L(f)) $ . Нижняя оценка $ n^2 $ на формульную сложность универсальной функции. Метод случайных подстановок Субботовской, нижняя оценка $ n^{1.5} $ для формул де Моргана для функции четности. Функция Андреева, нижняя оценка $ n^{2.5} $ для формул де Моргана.
6. Коммуникационная сложность и глубина схем (А. Головнёв)
(06.11.2011 - 13:00 - 14:35)

Коммуникационная сложность, игры Карчмера-Вигдерсона, покрытие прямоугольниками, связь с глубиной схем: $ cc(f)=D(f) $, монотонная глубина, примеры.
7. Монотонные формулы (Е. Деменков)
(06.11.2011 - 15:35 - 17:10)

Нижняя оценка через ранг матриц, нижняя оценка для квадратичных функций, суперполиномиальная нижняя оценка для функции Пэли.
8. Монотонные схемы (А. Кноп)
(20.11.2011 - 11:15 - 12:50)

Клики большого размера обнаружить в графе сложно, в то время как проверить, содержит ли граф клику очень большого размера, легко.
9. Отрицания в схемах (В. Алексеенко)
(20.11.2011 - 13:00 - 14:35)

Когда отрицания бесполезны? Функции среза, использование отрицаний переменных как новых переменных. Теорема Маркова: необходимое и достаточное число отрицаний для любой булевой функции. Для формул требуется экспоненциально большее количество отрицаний. Теорема Фишера: увеличив схему на $ O(n^2\log n) $, можно уменьшить количество отрицаний до $ \lceil \log (n+1) \rceil $. Сколько отрицаний достаточно для доказательства P$ \neq $NP?
10. Схемы глубины 3 (В. Рассохин)
(27.11.2011 - 13:00 - 14:35)

11. Схемы ограниченной глубины (Р. Колганов)
(11.12.2011 - 15:35 - 17:10)

Два способа доказательства нижних оценок на размеры схем ограниченной глубины: сокращение глубины с помощью леммы о переключении (Hastad's Switching Lemma) и аппроксимация схем полиномами маленькой степени. Примеры применения этих методов для схем, состоящих из чередующихся уровней AND и OR гейтов: получение с их помощью суперполиномиальной оценки на размеры таких схем, вычисляющих функции четности и голосования.
Ваша оценка: Пусто Средняя: 5 (14 votes)
Share |