Seminars

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



Квазиполиномиальный алгоритм Л.Бабаи для проверки изоморфизма графов. Краткое введение.

Speaker: 
И. Н. Пономаренко (ПОМИ РАН)
Date: 
Friday, September 23, 2016 - 17:30
Place: 
ПОМИ, ауд. 203
Abstract: 

Предполагается обсудить точное утверждение результата Бабаи, подход Лакса к проблеме изоморфизма графов и структуру алгоритма Бабаи (с высоты птичьего полета).



Lower and Upper Bound on Computational of Diameter in Distributed Networks

Speaker: 
Николай Карпов (ПОМИ)
Date: 
Monday, September 12, 2016 - 15:00
Place: 
ПОМИ, ауд. 402
Abstract: 

В докладе мы докажем нижние оценки на время работы распределенных алгоритмов вычисляющих диаметр графа или его приближения путем сведения к сложным задачам из коммуникационной сложности и продемонстрируем алгоритмы которые почти достигают этих оценок.



On the periodicity of multidimensional words of low complexity

Speaker: 
Jarkko Kari (University of Turku)
Date: 
Friday, September 2, 2016 - 17:00
Place: 
ПОМИ РАН, ауд. 106
Abstract: 

Let w : Z^d -> A be an infinite d-dimensional word over a finite alphabet A, and let D be a finite subset of Z^d, the d-dimensional integer grid. The D-patterns of w are the patterns of shape D that appear in w, that is, patterns t(w)|D where t spans over all translations. We say that w has low D-complexity if there are at most |D| distinct D-patterns in w. We study regularities enforced on w by such low complexity assumption. In particular, we are interested on periodicity, that is, whether there exists a non-trivial translation t such that t(w)=w. We use algebraic geometry to show that if w has low D-complexity for any D then w decomposes into a finite number of periodic components. We apply such decomposition to study Nivat's conjecture: the claim that if a two-dimensional w has low D-complexity for a rectangle D then w is periodic. We prove an asymptotic version that states that any two-dimensional non-periodic w can have low D-complexity only for finitely many distinct rectangles D.



Исследование критических наследственных классов графов

Speaker: 
Дмитрий Малышев (Высшая школа экономики)
Date: 
Thursday, April 14, 2016 - 12:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Одним из возможных способов преодоления алгоритмической сложности NP-полных задач на графах является сужение, т.е. наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений, т.е. принадлежности графа некоторому классу, приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается NP-полной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно, переходя от рассмотрения отдельных классов графов к рассмотрению каких-либо представительных семейств классов графов. В докладе рассматривается семейство наследственных классов графов, т.е. классов, замкнутых относительно удаления вершин. Также рассматриваются так называемые критические классы графов, т.е. классы графов, играющие особую роль в анализе сложности задач на графах в семействе наследственных классов. В докладе речь пойдет об известных критических классах для ряда задач на графах и соответствующих следствиях для анализа их сложности.



Sensetivity to Communication Complexity

Speaker: 
Дмитрий Соколов (ПОМИ)
Date: 
Monday, March 28, 2016 - 12:00
Place: 
ПОМИ, ауд. 402
Abstract: 

В докладе мы продемострируем метод получения сложный отношений, в смысле коммуницационной сложности, из функций с большой "block sensetivity".
Также покажем применение данного метода в сложности доказательств.


Pages