На факультете прошла конференция по теоретической информатике

14 июня на факультете состоялась однодневная конференция «Complexity of Computation, Communication, Descriptions and Proofs», организованная международной лабораторией теоретической информатики. Конференция прошла как смежное мероприятие с крупной международной конференцией «Computer Science in Russia».

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

В рамках конференции о результатах своих исследований рассказали ведущие зарубежные и российские учёные:

Amnon Ta-Shma (Tel-Aviv University), доклад: “Explicit, almost optimal, eps-balanced codes” о построении нового вида кодов с параметрами, близкими к оптимальным.

Bruno Loff (University of Porto), доклад: “Communication vs query complexity, new results” о соотношении между коммуникационной сложностью и запросной сложностью на примере задачи о вычислении композиции функций.

Stephen Fenner (The University of South Carolina), “Geometric approaches to derandomizing parallel matching and matroid algorithms” о последних результатах в области дерандомизации параллельных алгоритмов на графах и матроидах.

Дмитрий Соколов (ПОМИ РАН), доклад: “Monotone interpolation in proof complexity” об интерполяционном подходе для доказательства нижних оценок в пропозициональных системах доказательств.

Григорий Ярославцев (Indiana University, Bloomington), доклад: “Computational and communication complexity in massively parallel computing” о связи вычислительной и информационной сложности с недавно открытой моделью для массивных параллельных вычислений.

С более подробными аннотациями можно ознакомиться на странице конференции.

Также лабораторией было организовано два мини-курса: «Asymmetric Communication Complexity», «The matching problem: Approaches, applications, and algorithms». Их прочитали Bruno Loff и Stephen Fenner.

Видеозаписи мини курсов доступны на канале Youtube и в Вконтакте.