DM Seminar

Discrete Mathematics Seminar

Пятница, 9 апреля, 18-00, к. 106

Пятница, 9 апреля, ауд. 106. Начало в 18:00.

Докладчик: Александр Тискин (University of Warwick).

Тема: Тропические матрицы Монжа: Алгебраическая структура и алгоритмы.

Пятница, 12 февраля, 18-00, к. 106

Пятница, 12 февраля, ауд. 106. Начало в 18:00.

Докладчик: С. Николенко (ПОМИ РАН).

Тема: Схемная сложность и группы Томпсона-Хигмана.

Пятница, 29 января, 18:00, к. 106

Пятница, 29 января, ауд. 106. Начало в 18:00.

Докладчик: С. Нурк (СПбГУ).

Тема: О сложности задачи схемной выполнимости.

Пятница, 4 декабря, 18:00, к. 106

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

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

Тема: Криптографическая стойкость односторонней функции Голдрейха.

Пятница, 20 ноября, 18:00, к. 106

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

Докладчик: Н. В. Шилов (Новосибирск).

Тема: Joy of formal verification.

Пятница, 23 октября, 18:00, к. 106

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

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

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

Пятница, 16 октября, 18:00, к. 106

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

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

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

Пятница, 9 октября, 18:00, к. 106

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

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

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

Пятница, 18 сентября, 18:00, к. 106

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

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

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

Понедельник, 8 июня, 12:00, к. 106

Понедельник, 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.

Syndicate content