Laboratory of Mathematical Logic at PDMI

Пятница, 23 октября, комната 106. Начало в 18:00.

Докладчик: Д. Антипов.

Тема: Безусловное разделение классических классов сложности и классов сложности, использующих подсказку.

Пятница, 16 октября, комната 106. Начало в 18:00.

Докладчик: А. С. Охотин (университет Турку, Финляндия).

Тема: Конечные автоматы над однобуквенным алфавитом.

Пятница, 9 октября, комната 106. Начало в 18:00.

Докладчик: А. С. Куликов.

Тема: Нижняя оценка на схемную сложность.

Пятница, 18 сентября, комната 106. Начало в 18:00.

Докладчик: Н. Гравин.

Тема: Экономные механизмы для аукционов на покупку путей в графе.

Понедельник, 8 июня, комната 106. Начало в 12:00.

Докладчики: Sofya Raskhodnikova (Penn State University), Adam Smith (Penn State University).

Будет проведено 2 доклада:

Sofya Raskhodnikova (Penn State University) Transitive-closure Spanners

Adam Smith (Penn State University) What Can We Learn Privately?

Title: Transitive-closure Spanners.

Abstract

We define the notion of a transitive-closure spanner of a directed graph. A transitive-closure spanner of a given directed graph is a graph of small diameter that preserves connectivity of the original graph.

Пятница, 22 мая, комната 106. Начало в 17:50.

Докладчик: Д. Ицыксон.

Тема: Обращение функции Голдрейха алгоритмами, основанными на расщеплении.

Пятница, 15 мая, комната 106. Начало в 18:00.

Докладчик: Н. Гравин.

Тема: Линейные алгоритмы для задачи списковой -раскраски и задачи докрашивания частичной -раскраски.

Пятница, 24 апреля, комната 106. Начало в 18:00.

Докладчик: А. Смаль.

Тема: Миникурс: 'Логические основы теории сложности доказательств'. Лекция 3, заключительная.

Пятница, 17 апреля, комната 106. Начало в 18:00.

Докладчик: И. Миронов (Microsoft Research).

Тема: Differential Privacy.

Пятница, 27 марта, комната 106. Начало в 18:00.

Докладчик: А. Смаль.

Тема: Мини-курс: 'Логические основы теории сложности доказательств'. Лекция 2.