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

Примерная программа курса:

1. Представление булевых функций: КНФ, ДНФ, деревья решений, формулы, ветвящиеся программы, схемы. Нижние оценки для деревьев решений.
2. Схемы и машины Тьюринга. Сведение задачи выполнимости к КНФ. NP-полнота задачи SAT.
3. Деревья решений как доказательства невыполнимости формул в КНФ. Игры доказывающего и откладывающего. Древовидная резолюция.
4. Энтропия и однозначно-декодируемые коды. Коды Хаффмена.
5. Лемма Фаркаша. Теорема фон-Неймана о матричных играх.
6. Принцип Яо. Нижние оценки для вероятностных алгоритмов сортировки и вероятностных деревьев решений.
7. Коммуникационная сложность, прямоугольники. Time vs Space tradeoff для машин Тьюринга, вычисляющих палиндром.
8. Коды, исправляющие ошибки. Коды Хемминга, коды Адамара и Рида-Соломона. Вероятностная проверка произведения булевых матриц.
9. Вероятностная коммуникационная сложность предиката равенства.
10. Теорема Карчмара-Вигдерсона о связи коммуникационной сложности и формульной сложности. Оценка на формульную сложность Parity.