Коммуникационная сложность, прямоугольники. Сложность функции равенства. Time vs Space tradeoff для машин Тьюринга, вычисляющих палиндром. Теорема Карчмара-Вигдерсона о связи коммуникационной сложности и формульной сложности. Оценка на формульную сложность функции четности.

Коды, исправляющие ошибки. Коды Хемминга, коды Адамара и Рида-Соломона. Вероятностная коммуникационная сложность предиката равенства в случаи общих и приватных случайных битов.

Литература:

• E. Kushilevitz, N. Nisan, Communication Complexity
• А.Е. Ромащенко, А.Ю. Румянцев, А. Шень, Заметки по теории кодирования