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

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.

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