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.

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

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