В классической модели коммуникационной сложности на каждом раунде коммуникации один из игроков говорит (посылает бит), а другой его слушает. Мы предлагаем рассмотреть обобщение этой модели, в которой Алиса и Боб могут также говорить одновременно (и тогда они не слышат друг друга) или слушать одновременно. Естественный аналог такой модели — это общение по полудуплексному каналу, например при помощи рации. Мы рассматриваем три варианта такой обобщённой модели и доказываем верхние и нижние оценки на коммуникационную сложность булевых функций в них.

По совместной работе с Иваном Михайлиным, Кеном Хувером и Расселом Импальяццо.

В докладе будут представлены семантические одноразовые ветвящиеся программы. Для таких ветвящихся программ на любом пути из стартовой вершины до 1-стока, если этот путь соответствует корректной подстановке, каждая переменная должна встречаться не более одного раза. На остальных же путях переменные могут повторяться. Для недетерминированных семантических одноразовых ветвящихся программ, вычисляющих булевы функции, которые можно вычислить за полиномиальное время, пока не известны нижние экспоненциальные оценки.

Мы рассмотрим доказательство экспоненциальной нижней оценки для недетерминированных семантических 3-арных одноразовых ветвящихся программ — в таких программах каждой вершине диаграммы может соответствовать 3 различных значения.

Доклад по одноимённой работе Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi.

Бесконечнозначная логика Лукасевича первого порядка \L$\forall$ и
её расширение рациональными истинностными константами --- рациональная логика Павелки первого порядка RPL$\forall$ --- являются одними из важнейших математических нечётких логик, формализующих приближённые рассуждения. В докладе мы представим ориентированное на поиск вывода снизу вверх гиперсеквенциальное исчисление GRP$\forall$ для RPL$\forall$, каждое правило которого обратимо и
не имеет ни в какой посылке повторений обозначений мультимножеств формул. Сравним (с точки зрения выводимости) GRP$\forall$ с другими исчислениями для \L$\forall$ и RPL$\forall$. Установим некоторые теоретико-доказательственные свойства GRP$\forall$, чем обеспечим основания для алгоритмов поиска вывода. Наконец, опишем семейство алгоритмов поиска вывода в табличном варианте исчисления GRP$\forall$.