Seminars

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



Пятница 24.03. Д. Соколов: "Нижние оценки в Cutting Planes"

Speaker: 
Д. Соколов
Date: 
Friday, March 24, 2017 - 17:30
Place: 
Ауд. 203
Abstract: 

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

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



Среда 22.03. Reinhard Diestel: "Tangles and the Mona Lisa: connectivity versus tree structure"

Speaker: 
Reinhard Diestel
Date: 
Wednesday, March 22, 2017 - 14:00
Place: 
ауд. 203
Abstract: 

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.



Пятница 17.03. Александр Рыбалов: "Генерический подход к алгоритмическим проблемам"

Speaker: 
Александр Рыбалов
Date: 
Friday, March 17, 2017 - 17:15
Place: 
ауд. 203
Abstract: 

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



Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.



Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.


Pages