Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Пятница 12.05. Alexei Miasnikov (Stevens Institute): "Hard instances, Dehn monsters, and complexity"

Speaker: 
Alexei Miasnikov (Stevens Institute)
Date: 
Friday, May 12, 2017 - 18:00
Place: 
203
Abstract: 

In this talk I will focus on two seemingly different directions in modern algorithmic group theory: finding more and more efficient algorithms and how to find "hard" instances of the problems, how to amplify hardness, and how to measure hardness of the algorithms. The talk is intended to be non-technical, I will emphasize some relations between algorithmic group theory and cryptography.



Пятница 21.04. Николай Мальковский (СПбГУ): "Распределенный алгоритм решения задачи о максимальном потоке"

Speaker: 
Николай Мальковский (СПбГУ)
Date: 
Friday, April 21, 2017 - 17:15
Place: 
ауд. 203
Abstract: 

Задача о максимальном потоке и её двойственная -- задача о минимальном разрезе -- являются одними из наиболее изучаемых задач теории графов, на практике эти задачи часто встречаются в качестве промежуточных вычислений. В отдельных случаях возникает потребность решения задачи о максимальном потоке на вычислительной распределенной сети, где графом является топология взаимодействия этой сети. В таких ситуациях возникает вопрос: а можно ли решить задачу о максимальном потоке методом, не требующим синхронизации или сбора всей информации на одном из узлов сети? Алгоритмы, решающие какую-либо задачу в сети с такими ограничениями, обычно называются "распределенными". Как пример, задача синхронизации времени в сети допускает только распределенные методы решения. В докладе пойдет речь об одном распределенном алгоритме решения задачи о максимальном потоке и его связи с методами, основанными на электрических потоках и решении лапласиановых систем.



Понедельник 17.04. А.Е. Ромащенко (LIRMM): "О геометрических и комбинаторных интерпретациях условных информационных неравенств"

Speaker: 
А.Е. Ромащенко (LIRMM)
Date: 
Monday, April 17, 2017 - 17:00
Place: 
106
Abstract: 

Следуя Н.Пиппенжеру, можно сказать, что наиболее общие "законы теории информации" выражаются в терминах линейных неравенств для энтропии Шеннона. Классические неравенства для энтропии (монотонность, субаддитивность, субмодулярность) восходят к работе К.Шеннона 1948 г. Эти неравенства имеют ясный интуитивный смысл. Например, субаддитивность энтропии $H(X,Y) \le H(X)+H(Y)$ означает, что "количество информации", заключенное в паре случайных величин (X,Y), не превосходит суммы объемов информации в X и Y соответственно. Известны многочисленные применения информационных неравенств. Каждое линейное неравенство для энтропии можно эквивалентным образом переформулировать на многих разных языках: как утверждения о конечных группах, о колмогоровской сложности, о размерах проекций конечных множеств, и т.д.

Известны и более экзотические утверждения о шенноновской энтропии -- так называемые условные информационные неравенства (constraint information inequalities). Каждое такое неравенство выполнено при некотором ограничении на рассматриваемые случайные величины. Например, неравенство Инглетона для энтропий четверки случайных величин (A,B,C,D) выполняется при условии I(A:B) = I(A:B|C) = 0. Известно лишь несколько нетривиальных примеров условных информационных неравенств, и до недавнего времени они казались бессодержательными артефактами определения энтропии.

Мы покажем, что условные информационные неравенства могут иметь вполне содержательный смысл и интересные применения. Мы обсудим связь условных неравенств с теоремой Матуша (конус энтропийных точек не полиэдрален), с бикликовым покрытием графа (оценки Куликова--Юкны) и некоторыми оценками для раскраски графов (Верещагин--Касед).



Пятница 07.04. А. Кноп: "Задача поиска и диаграммы принятия решений"

Speaker: 
А. Кноп
Date: 
Friday, April 7, 2017 - 17:15
Place: 
203
Abstract: 

Классический результат Хватала и Семереди гласит, что размер древесного доказательства равен минимальному размеру дерева ищущему невыполненный клоз и аналогичное утверждение верно для регулярных резолюций и для 1-BP.

Однако подобные результаты для более сложных классов диаграмм не были известны. В докладе мы рассмотрим системы доказательств похожие на систему доказательств IPS. Доказаны результаты об эквивалентности доказательств в этих системах и задач поиска невыполненного клоза, а так же доказаны нижние и верхние оценки в данных системах.



Пятница 31.03. Станислав Сперанский (СПбГУ): "О сложности «элементарных» теорий различных классов вероятностных пространств"

Speaker: 
Станислав Сперанский (СПбГУ)
Date: 
Friday, March 31, 2017 - 17:15
Place: 
ауд. 203
Abstract: 

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

Приглашаются все желающие.

Список основной литературы:

S.O. Speranski (2016). Quantifying over events in probability logic: an introduction. Mathematical Structures in Computer Science, published online.
S.O. Speranski (2013). Complexity for probability logic with quantifiers over propositions. Journal of Logic and Computation 23:5, 1035–1055.
R. Fagin, J.Y. Halpern and N. Megiddo (1990). A logic for reasoning about probabilities. Information and Computation 87:1–2, 78–128.


Pages