[ONLINE] Семинар МЛ ТИ: "Формульная сложность и гипотеза Карчмера - Раза - Вигдерсона"

27 января Александр Смаль (ПОМИ РАН) выступит  на семинаре лаборатории теоретической информатики с докладом на тему «Формульная сложность и гипотеза Карчмера - Раза - Вигдерсона».

 Дата проведения: 27 января, четверг.
Время проведения: с 18:10 до 19:30.
Место проведения: онлайн
Zoom:  https://zoom.us/j/98461629579?pwd=TFJPT20xLzhwc1lCeWlQZ200dFo0QT09

 Аннотация:
Одна из основных открытых задач формульной сложности - это доказательство суперкубической оценки на размер формулы для явной булевой функции. Наилучшая известная оценка такого вида - это кубическая оценка Хостада для функции Андреева, которая была получена более 20 лет назад. Один из возможных подходов к этой задаче - это реализация программы, предложенной Карчмером, Разом и Вигдерсоном, которая потенциально может привести в доказательству суперполиномиальной нижней оценки для функции из класса P, из чего будет следовать разделение сложностных классов P и NC1.

На семинаре мы поговорим про эту программу, заключающуюся в доказательстве гипотезы Карчмера - Раза - Вигдерсона, и обсудим, каких успехов удалось добиться на этом пути.