Laboratory of Mathematical Logic at PDMI

Пятница, 22 декабря, 402. Начало в 13:00.

Докладчик: Д.О. Соколов.

Тема: Monotone Circuit Lower Bounds from Resolution.

Abstract

Для любой формулы, которая сложна для резолюций, мы покажем что если заменить каждую переменную на функцию индексирования от новых переменных, то получится формула, которая является сложной для любой
семантической системы доказательств, строки которой могут быть вычислены эффективным коммуникационным протоколом (CP^*, CP, ...).

Данный результат представляет собой так называемую "lifting theorem" для графа запросов и коммуникационных протоколов на графах.

Доклад по совместной работе с Ankit Garg, Mika Göös и Pritish Kamath.

Внимание! Ориентировочная продолжительность доклада 2 пары: с 13-00 до 14-40 и с 16-00 до 17-40.