Миникурс по сложности пропозициональных доказательств. Лекция 2.

Миникурс по сложности пропозициональных доказательств. Лекция 2.

Докладчик:

Д.М. Ицыксон, А.А. Кноп

Дата:

Friday, November 18, 2016 - 17:30

Аннотация:

В первой части будет окончание предыдущей лекции, из теоремы Бен-Сассона и Вигдерсона будут выведены нижние оценки на цейтинские формулы и принцип Дирихле.
Во второй части А.А. Кноп расскажет про то, как нижние оценки для древовидных доказательств можно вывести из известных нижних оценок для коммуникационной сложности функции Disjointness.