Seminars

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



Пятница 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.



Пятница 17.03. Александр Рыбалов: "Генерический подход к алгоритмическим проблемам"

Speaker: 
Александр Рыбалов
Date: 
Friday, March 17, 2017 - 17:15
Place: 
ауд. 203
Abstract: 

Генерический подход к вычислимости и вычислительной сложности был предложен И.Каповичем, А.Мясниковым, В.Шпильрайном и П.Шуппом в 2003 г. В рамках этого подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве "почти всех" входов. Такие входы образуют так называемое генерическое множество. Понятие "почти все" формализуется введением естественной меры на множестве входных данных. Данный подход схож с изучением сложности в среднем, но, в отличие от него, "плохие входы" игнорируются - алгоритм на них выдает ответ "не знаю". Это позволяет, также изучать генерическую сложность неразрешимых проблем. В докладе будет дан обзор результатов по генерической сложности различных классических проблем.


Pages