Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 28 октября 2017, 15:20–18:30
Где: 2-й учебный корпус К(П)ФУ, ауд. 109

Описание

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

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

Литература: