Для системы доказательств CP известен только один метод доказательства нижних оценок --- метод интерполяции, т.е. построение по короткому доказательству в CP короткой монотонной схемы для подсчета некоторой функции. Таким образом, чтобы доказать нижнюю оценку для CP достаточно доказать нижнюю оценку на монотонные схемы. Одной из существенных проблем данного метода является то, что он может быть применен лишь к узкому классу формул. В докладе мы обобщим метод интерполяции на формулу произвольного вида и докажем нижнюю оценку для случайной log(n)-КНФ формулы.

Доклад по статье:
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
Random CNFs are Hard for Cutting Planes

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.

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