Seminars

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



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



Пятница 24.03. Д. Соколов: "Нижние оценки в Cutting Planes"

Speaker: 
Д. Соколов
Date: 
Friday, March 24, 2017 - 17:30
Place: 
Ауд. 203
Abstract: 

Для системы доказательств CP известен только один метод доказательства нижних оценок --- метод интерполяции, т.е. построение по короткому доказательству в CP короткой монотонной схемы для подсчета некоторой функции. Таким образом, чтобы доказать нижнюю оценку для CP достаточно доказать нижнюю оценку на монотонные схемы. Одной из существенных проблем данного метода является то, что он может быть применен лишь к узкому классу формул. В докладе мы обобщим метод интерполяции на формулу произвольного вида и докажем нижнюю оценку для случайной log(n)-КНФ формулы.

Доклад по статье:
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
Random CNFs are Hard for Cutting Planes



Среда 22.03. Reinhard Diestel: "Tangles and the Mona Lisa: connectivity versus tree structure"

Speaker: 
Reinhard Diestel
Date: 
Wednesday, March 22, 2017 - 14:00
Place: 
ауд. 203
Abstract: 

Tangles, first introduced by Robertson and Seymour in their work on graph minors, are a radically new way to define regions of high connectivity in a graph. The idea is that, whatever that highly connected region might `be', low-order separations of the graph cannot cut through it, and so it will orient them: towards the side of the separation on which it lies. A tangle, thus, is simply a consistent way of orienting all the low-order separations in a graph.

The new paradigm this brings to connectivity theory is that such consistent orientations of all the low-order separations may, in themselves, be thought of as highly connected regions: rather than asking exactly which vertices or edges belong to such a region, we only ask where it is, collecting pointers to it from all sides.

Pixellated images share this property: we cannot tell exactly which pixels belong to the Mona Lisa's nose, rather than her cheek, but we can identify `low-order' separations of the picture that do not cut right through such features, and which can therefore be used collectively to delineate them.

This talk will outline a general theory of tangles that applies not only to graphs and matroids but to a broad range of discrete structures. Including, perhaps, the pixellated Mona Lisa.


Pages