Просмотр кода страницы Сложность вычислений и логика в теоретической информатике

= Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2019 год =

Лекции проходят по вторникам в аудитории 501 в 10:30-11:50. Семинары по вторникам  в аудитории 501 в 12:10-13:30. Первая лекция и семинар 15 января.

'''[https://t.me/joinchat/GQufoBIS_oUktcWHuqSjZg Группа в телеграме для вопросов]'''

==Новости==

29.1.2019 Выложено первое дз.

==Лектор== 

Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com

==Семинарист== 

Козачинский Александр Николаевич, kozlach@mail.ru



==Краткое описание==

Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, экспандерные коды.

Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и 
поля комплексных чисел. 

Представление булевых функций деревьями разрешения и многочленами. 

Лемма Ловаса и быстрые алгоритмы для SAT.

Сложность булевых схем.

==Отчётность по курсу и критерии оценки==

4 домашних задания, коллоквиум и экзамен.

Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.
Сдача домашних заданий после их срока невозможна.

Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме  не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. 

Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.   

====Правила округления==== 

В вычислениях текущие оценки и промежуточные величины не округляются. Результат
вычисляется точно и округляется (арифметически) только в момент выставления накопленной и итоговой оценок.

====Коллоквиум====

Коллоквиум состоится 10 июня в 13:30-16:30 в ауд. 400, а также 17 июня в 12:10-15 в ауд. 618.
[https://www.dropbox.com/s/hw20q0dtd2pxoyq/colloq2019.pdf?dl=0 Программа коллоквиума.]

====Экзамен====

Письменный состоится в  22 июня в 10:30--13:30 в ауд. 400. Показ работ 22 июня в 16:40.

====Пересдачи====

Пересдачи (письменные) состоятся 17 сентября и 1 октября в 15:10 в ауд. S832. Сдача экзамена комиссии - 8 котября в 15:10.

==Примерные сроки контрольных мероприятий==

Первое домашнее будет выложено 29.1.2019, срок сдачи 12.2.2019.

Второе домашнее будет выложено 5.3.2019, срок сдачи 02.4.2019.

Третье домашнее будет выложено 9.4.2019, срок сдачи 23.4.2019.

Четвертое домашнее будет выложено 14.5.2019, срок сдачи 28.5.2019.

==Домашние задания  ==

''Скорее всего, во всех дз будет по 2 бонусных задачи. Каждая из них дает +1 к оценке коллоквиума или экзамена, по выбору студента.  Чтобы бонус засчитался, нужно за основную часть ДЗ получить не менее половины от максимально возможного балла.''

[https://www.dropbox.com/s/zhm6lzkimton7k3/results_2019.xlsx?dl=0 Оценки]

[https://www.dropbox.com/s/q2xzohnb5bqs83k/hw_1.pdf?dl=0 Домашнее задание 1.] Cрок сдачи 12.2.2019 в 12:10 MSK.

[https://www.dropbox.com/s/xx5nun615qm2591/hw_2.pdf?dl=0 Домашнее задание 2.] Срок сдачи 02.4.2019 в 12:10 MSK.

[https://www.dropbox.com/s/yrrpzd7ws2jxb9z/hw_3.pdf?dl=0 Домашнее задание 3.] Срок сдачи 30.4.2019 в 12:10 MSK.

[https://www.dropbox.com/s/jt78vj3un9jg070/hw_4.pdf?dl=0 Домашнее задание 4.] Срок сдачи до коллоквиума.

==Прочитанные лекции==



====Лекция 1 (15 января).  ====

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.

====Лекция 2 (22 января).  ====

Лемма о перемешивании. От спектрального экспандера к комбинаторному.

====Лекция 3 (29 января).  ====

Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. 
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.

====Лекция 4 (5 февраля). ====

Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.

====Лекция 5 (12 февраля). ====

Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.

Вторая оценка для спекртальной щели зигзаг-произведения.

Алгоритм Рейнгольда.

====Лекция 6 (19 февраля). ====
Алгоритм Рейнгольда.
Применение экспандеров для дерандомизации.

====Лекция 7 (26 февраля). ====

Экспандер Маргулиса.

====Лекция 8 (5 марта). ====

Экспандер Маргулиса (окончание доказательства).

Двудольные экспандеры: определение и вероятностное доказательство существования.

====Лекция 9 (12 марта). ====

Экспандер Варди - Парвареша.

====Лекция 10 (19 марта). ====

Экспандерные коды: определение, параллельный и последовательный алгоритмы декодирования.
====Лекция 11 (2 апреля). ====

Разрешимость элементарной теории поля комплексных чисел.

====Лекция 12 (9 апреля). ====
Разрешимость элементарной теории упорядоченного поля
действительных чисел.

====Лекция 13 (16 апреля). ====

Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность.
Чувстительность и блочная чувствительность. 
Неравенства D < C_0 C_1, D< C_0 bs_1

====Лекция 14 (23 апреля). ====

Неравенство C_0< bs_0 s_1. Вероятностные деревья и неравенство bs = O(R)

Представление булевых функций многочленами с действительными коэффициентами.

Теорема Маркова.

====Лекция 15 (30 апреля). ====

Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).

Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ

Связь между размером дерева и представлением функции в виде m,*-ДНФ и m,*-КНФ (Эренфойхт - Хауслер).

====Лекция 16 (14 мая). ====

Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).

Метод Храпченко доказательства нижних оценок формульной сложности.

====Лекция 17 (21 мая). ====

Ограничения булевой функции. Нижняя оценка формульной сложности функции Андреева.

Теорема Разборова - Смоленского о нижней оценке размера формул ограниченной глубины.

====Лекция 18 (28 мая). ====

Коды с исправлением ошибок и их параметры. Линейные коды.

Оценка Синглтона и коды Рида - Соломона.
Декодирование кодов Рида - Соломона.

====Лекция 19 (4 июня). ====

Оценка Хэмминга и коды Хэмминга (без доказательства и построения)

Случайные коды и оценка Варшамова - Гилберта. 
Коды Возенкрафта.

====Лекция 20 (11 июня). ====

Каскадные коды и коды Форни. Декодирование каскадного кода.

==Задачи для семинаров  ==


'''[https://www.dropbox.com/s/mr072cifyo8gwou/listok1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]'''

'''[https://www.dropbox.com/s/mp1ki1l1gr57u7k/listok2.pdf?dl=0 Листок 2  (еще комбинаторные экспандеры)]'''

'''[https://www.dropbox.com/s/ts0c25lkv4904vr/listok3.pdf?dl=0 Листок 3  (спектр графов)]'''

'''[https://www.dropbox.com/s/2r8414hb714t63k/listok4.pdf?dl=0 Листок 4  (спектр графов и спектральные экспандеры)]'''

'''[https://www.dropbox.com/s/m1grmoyst9ob6dg/listok5.pdf?dl=0 Листок 5  (случайные блуждания)]'''

'''[https://www.dropbox.com/s/hxuhzdkov857vin/listok6.pdf?dl=0 Листок 6  (log-space алгоритмы)]'''

'''[https://www.dropbox.com/s/di35x1lk5m6o2ck/listok7.pdf?dl=0 Листок 7  (продолжаем спектральные экспандеры)]'''

'''[https://www.dropbox.com/s/ovlo3e3g9d58rad/listok8.pdf?dl=0 Листок 8  (аффинная плоскость и другие экспандеры)]'''

'''[https://www.dropbox.com/s/hc5pl51oyh66o3k/listok9.pdf?dl=0 Листок 9  (двудольные экспандеры)]'''

'''[https://www.dropbox.com/s/o3q2tm3a90zrho0/listok10.pdf?dl=0 Листок 10 (болты и гайки)]'''

'''[https://www.dropbox.com/s/fs9w2gh3kwbz5wb/listok11.pdf?dl=0 Листок 11 (выразимость, элиминация кванторов)]'''

'''[https://www.dropbox.com/s/mzkm72hplcwb7js/listok12.pdf?dl=0 Листок 12 (еще элиминация кванторов)]'''

'''[https://www.dropbox.com/s/222ezqqshecm8b7/listok14.pdf?dl=0 Листок 14 (еще деревья разрешения)]'''

'''[https://www.dropbox.com/s/znhfveu6cxi3n3r/listok15.pdf?dl=0 Листок 15 (деревья разрешения + немного схем)]'''

'''[https://www.dropbox.com/s/8l2szgu7t7gzoez/listok16.pdf?dl=0 Листок 16 (схемы)]'''

'''[https://www.dropbox.com/s/t9689386f5c89kv/listok17.pdf?dl=0 Листок 17 (еще схемы)]'''

'''[https://www.dropbox.com/s/nvj71sfc4juo4v9/listok18.pdf?dl=0 Листок 18 (схемы + коды)]'''

'''[https://www.dropbox.com/s/ygyjf2wm7jtxb24/listok19%20-%20%D0%BA%D0%BE%D0%BF%D0%B8%D1%8F.pdf?dl=0 Листок 19 (коды)]'''

==Семинары  ==

=== Семинар 1 (15 января) ===

Разобраны задачи 1-5 из первого листка. Кроме этого, частично разобрана задача 7.

=== Семинар 2 (22 января) ===

Решены задачи 1 и 4.

=== Семинар 3 (29 января) ===

Решены задачи 1, 4 и 6а, а также 5 в одну сторону.

=== Семинар 4 (5 февраля) ===

Решили задачи 4 и 5. Для этого рассказал о графах Кели.

=== Семинар 5 (12 февраля) ===

Решена задача 4. Решали 5-ую, но не до конца.

=== Семинар 6 (19 февраля) ===

Решили все задачи из листка.

=== Семинар 7 (26 февраля) ===

Решили первую и часть четвертой задачи.

=== Семинар 8 (5 марта) ===

Решили первые три задачи.

=== Семинар 9 (12 марта) ===

Решена первая задача.

=== Семинар 10 (19 марта) ===

Решена первая задача. Остальное время обсуждали 2-ую задачу.

=== Семинар 11 (2 апреля) ===

Решены задачи 1, 2a, 4.

=== Семинар 12 (9 апреля) ===

Решены задачи 1, 2а, 2б, 3а, 6а.

=== Семинар 13 (16 апреля) ===

Решены задачи 1, 2, 4.

=== Семинар 14 (23 апреля) ===

Решены задачи 1 и 4а)

=== Семинар 15 (30 апреля) ===

Разобрали первую задачи + обсудили схемы, отношения Карчмера --- Видгерсона, как доказать, что для Majority нужна глубина хотя бы 2\log_2(n).

=== Семинар 16 (14 мая) ===

Решили задачи 1, 2 и 3а.

=== Семинар 17 (21 мая) ===

Решили задачи 1 и 2.

=== Семинар 18 (28 мая) ===

Решили 5 задачу и частично 6а)

=== Семинар 19 (4 июня) ===

==Конспекты лекций==
[https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко]

[https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0 Конспект лекций о деревьях разрешения.]

[https://www.dropbox.com/s/ofsc0q70yg9ptsp/all.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."

==Рекомендуемая литература  ==

[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]

[https://arxiv.org/abs/0903.0544 Moser  R.A.,  Tardos  G.,  A  constructive  proof  of  the  general  Lovasz  Local  Lemma,Journal of the ACM, 2010, 57(2), 11.1–11.15.]

[https://arxiv.org/pdf/1305.1535.pdf Статья Румянцева и Шеня с изложением алгоритма Мозера-Тардоша]

[https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995] 

N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.

Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014.  https://eccc.weizmann.ac.il/report/1999/014/

[http://www.cs.columbia.edu/~rocco/Teaching/S17/6998/Boppana-Sipser.pdf Ravi B. Boppana, Michael Sipser. The Complexity of Finite Functions.]
(Обзор Алона и Боппаны с изложением доказательства теоремы Разборова - Смоленского, метода ограничений и леммы Субботовской, и нижней оценки формульной сложности функции Андреева.)