Seminars

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



Monotone real circuit

Speaker: 
Дмитрий Соколов (ПОМИ)
Date: 
Friday, September 30, 2016 - 14:00
Place: 
ПОМИ, ауд. 402
Abstract: 

В докладе рассмотрим доказательство нижних оценок на монотонные вещественные схемы для функции Broken Mosquito Screen. Доказательство основано на построениие заборов и идейно отличается от доказательства Разборова для Clique-Coloring.
Также мы докажем нижнюю оценку на Cutting Plane не ссылаясь на доказательство Пудлака.



An Information Complexity Approach to the KRW Composition Conjecture

Speaker: 
Александр Смаль (ПОМИ)
Date: 
Monday, September 26, 2016 - 15:00
Place: 
ПОМИ, ауд. 402
Abstract: 

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $ P \not \subset NC^1 $). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds.

Karchmer, Raz, and Wigderson [KRW95] suggested to approach this problem by proving the following conjecture: given two Boolean functions $ f $ and $ g $, the depth complexity of the composed function gf is roughly the sum of the depth complexities of $ f $ and $ g $. They showed that the validity of this conjecture would imply that $ P \not \subset NC^1 $.

As a starting point for studying the composition of functions, they introduced a relation called "the universal relation", and suggested to study the composition of universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Håstad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation.



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

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.


Pages