Search
Пятница 18.11. Д.М. Ицыксон, А.А. Кноп: "Миникурс по сложности пропозициональных доказательств. Лекция 2"
Пятница, 18 ноября, ауд. 203. Начало в 17:15.
Докладчик: Д.М. Ицыксон, А.А. Кноп.
Тема: Миникурс по сложности пропозициональных доказательств. Лекция 2.
Abstract
В первой части будет окончание предыдущей лекции, из теоремы Бен-Сассона и Вигдерсона будут выведены нижние оценки на цейтинские формулы и принцип Дирихле.Во второй части А.А. Кноп расскажет про то, как нижние оценки для древовидных доказательств можно вывести из известных нижних оценок для коммуникационной сложности функции Disjointness. (Это результат Бима, Питасси и Сегерлинда в изложении Гуса и Питасси 2014 года)