Сложность булевых функций

Общая информация
ЛекторВ. В. Подольский
Семестросень 2014
Дата начала25.10.2014
Количество пар10
Язык курсарусский
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/24696
Аннотация

В рамках курса планируется рассказать об одном из основных направлений теории сложности вычислений — схемной сложности булевых функций.

Формальное изучение этой области началось еще в первой половине двадцатого века, то есть очень давно по меркам Computer Science. Бум развития схемной сложности пришелся на 80-е годы и был связан с идеей использования нижних оценок размера булевых схем, как подхода к проблеме о сложностных классах P и NP. Этот этап развития области привел к ряду прорывных результатов, новых методов и идей. Однако, оказалось, что получить решение проблемы о P и NP на этом пути (как и на всех других) не так просто. Более того, было доказано, что для решения этой проблемы посредством булевых схем нужны кардинально новые методы, и текущих методов принципиально не достаточно. В настоящее время работа в области схемной сложности продолжается, в последние годы был получен ряд интересных результатов.

В курсе будет дано введение в теорию схемной сложности булевых функций, рассказано о некоторых ключевых результатах в области, а также о связях с другими моделями вычислений. Основной акцент планируется сделать на методах доказательства нижних оценок в схемной сложности.

Также мы попробуем показать, как результаты теории схемной сложности, могут применяться к другим областям Computer Science, на примере вопросов о сложности обработки запросов к онтологическим базам данных.

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

1. Булевы схемы и формулы
(25.10.2014 - 17:20 - 18:55)

Определение булевых схем и булевых формул, введение. Взаимосвязь глубины и размера формул. http://www.youtube.com/watch?v=GDWdmL01qqo
2. Булевы формулы и коммуникационная сложность
(25.10.2014 - 19:00 - 20:35)

Характеризация глубины булевых схем с помощью коммуникационной сложности. http://www.youtube.com/watch?v=2dYXHn155n4#t=692
3. Монотонные формулы для задачи "Достижимость", сведение к коммуникационным играм
(26.10.2014 - 11:15 - 12:50)

Начало доказательства нижней оценки $ \Omega(\log^2 n) $ глубины монотонных формул для задачи достижимости в ориентированном графе. Сведение к коммуникационной сложности. http://www.youtube.com/watch?v=mGagIbPJk7U#t=268
4. Монотонные формулы для задачи "Достижимость", нижняя оценка
(26.10.2014 - 13:00 - 14:35)

Завершение доказательства нижней оценки $ \Omega(\log^2 n) $ глубины монотонных формул для задачи достижимости в ориентированном графе. Оценка коммуникационной сложности. http://www.youtube.com/watch?v=JyC7_5Xe73o
5. Монотонные формулы для функций "Паросочетание" и "Клика"
(26.10.2014 - 15:35 - 17:10)

Нижняя оценка $ \Omega(n) $ глубины монотонных формул для функций "Паросочетание" и "Клика". http://www.youtube.com/watch?v=6mc6Q3EuPvk
6. Нижняя оценка для монотонных схем, начало
(01.11.2014 - 17:20 - 18:50)

Начало доказательства нижней оценки $ 2^{\Omega(n^{\epsilon})} $ размера монотонных схем для функции "Клика": функция "Клика" не приближается дизъюнкцией малого числа индикаторных функций. http://www.youtube.com/watch?v=RGdE4CNQMv4#t=66
7. Нижняя оценка для монотонных схем, окончание
(01.11.2014 - 19:00 - 20:30)

Завершение доказательства нижней оценки $ 2^{\Omega(n^{\epsilon})} $ размера монотонных схем для функции "Клика": монотонные схемы маленького размера приближаются дизъюнкцией малого числа индикаторных функций. http://www.youtube.com/watch?v=exYW1EznU_k
8. Приложение: онтологические базы данных
(02.11.2014 - 11:15 - 12:50)

Приложение результатов о сложности булевых схем для оценки длин преобразований запросов к онтологическим базам данных. http://www.youtube.com/watch?v=exNSoHU7cjY
9. Схемы ограниченной глубины: приближение многочленами
(02.11.2014 - 13:00 - 14:35)

Нижняя оценка $ 2^{\Omega(n^\epsilon)} $ размера схем постоянной глубины в базисе из отрицаний, конъюнкций, дизъюнкций и сложения по модулю 3, вычисляющих функцию сложения по модулю 2. http://www.youtube.com/watch?v=yN5hdPvr1As
10. Пороговые схемы
(02.11.2014 - 15:35 - 17:10)

Пороговые схемы, введение. Нижняя оценка $ n/2 $ размера пороговых схем для функции "Скалярное произведение". http://www.youtube.com/watch?v=pBFe5nlAi9M
Ваша оценка: Пусто Средняя: 4.5 (8 votes)
Share |
Владимир Подольский
Владимир Подольский
Владимир Подольский
Владимир Подольский и студенты