Seminars

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



Исследование критических наследственных классов графов

Speaker: 
Дмитрий Малышев (Высшая школа экономики)
Date: 
Thursday, April 14, 2016 - 12:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

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



Sensetivity to Communication Complexity

Speaker: 
Дмитрий Соколов (ПОМИ)
Date: 
Monday, March 28, 2016 - 12:00
Place: 
ПОМИ, ауд. 402
Abstract: 

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



Вычислительная сложность полиномиальных задач

Speaker: 
Николай Карпов (ПОМИ/АУ)
Date: 
Monday, February 29, 2016 - 16:00
Place: 
ПОМИ, ауд. 402
Abstract: 

Есть ансамбль практических задач, которые мы умеем решать за полиномиальное время. Однако, почти везде наивный алгоритм является наиболее быстрым для этих задач и существенное
улучшение этих алгоритмов открытая задача. Есть три популярные гипотезы, которые позволяют доказывать нижние оценки (в предположении трудности классических задач) на время работы алгоритмов: SETH, APSP не решается за субкубическое время, 3SUM не решается за субквадтратичное время. Планируется рассказать о различных задачах на графах и что они не легче чем APSP. Например, почему найти все треугольники отрицательного веса в графе не легче чем посчитать все кратчайшие расстояния между парами вершин. В некоторых задачах даже поиск приближенного решения с константной ошибкой не легче поиска точного решения и причины этого мы тоже постараемся узнать.



Эквивалентность вложений в L_p и скетчей для норм

Speaker: 
Илья Разенштейн (MIT)
Date: 
Friday, January 22, 2016 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Imagine the following communication task. Alice and Bob each have a point from a metric space. They want to transmit a few bits and decide whether their points are close to each other or are far apart. Of particular interest are sketching protocols: Alice and Bob both compute short summaries of their inputs and then a referee, given these summaries, makes the decision; sketches are very useful for the nearest neighbor search, streaming, randomized linear algebra etc. Indyk (FOCS 2000) showed that for the l_p spaces with 0 < p <= 2 the above problem allows a very efficient sketching protocol. Consequently, any metric that can be mapped into the l_p space with all the distances being approximately preserved has a good protocol as well.

I will show that for normed spaces (a very important class of metric spaces) embedding into l_p is the only possible technique for solving the communication problem. Slightly more formally, we show that any normed space that admits a good communication (in particular, sketching) protocol for distinguishing close and far pairs of points embeds well into l_p with p being close to 1. The proof uses tools from communication complexity and functional analysis.

As a corollary, we will show communication lower bounds for the planar Earth Mover's Distance (minimum-cost matching metric) and for the trace norm (the sum of the singular values of a matrix) by deriving them from the (known) non-embeddability theorems and (the contrapositive of) our result.

The talk is based on a joint paper with Alexandr Andoni and Robert Krauthgamer (arXiv:1411.2577).



Алгоритмы и оценки в тропической алгебре

Speaker: 
Дмитрий Юрьевич Григорьев (Institut des Mathématiques de Lille)
Date: 
Tuesday, August 25, 2015 - 18:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Предполагается дать обзор алгоритмов и оценок сложности в тропической математике – интенсивно развивающейся области, имеющей как общие, так и отличные черты от классической математики.

Для классических систем линейных уравнений алгоритм Гаусса имеет полиномиальную сложность. Для систем линейных уравнений над тропическим полукольцом существование подобного алгоритма – открытая несколько десятилетий проблема, известны лишь алгоритмы со сложностью близкой к полиномиальной. Для классических линейных систем их разрешимость определяется рангом матрицы, в тропическом случае имеется несколько определений ранга. Также доказано совместно с В.Подольским, что задача совпадения предмногообразий решений тропических линейных систем эквивалентна задаче разрешимости систем (это отвечает на вопрос В. Воеводского). С другой стороны, мы показали, что в отличие от классического случая, задача вычисления размерности линейного тропического предмногообразия NP-­полна.

Классическая теорема Гильберта о нулях (в двойственной форме) сводит разрешимость системы полиномиальных уравнений к разрешимости системы линейных уравнений с матрицей Маколея. Совместно с В.Подольским мы доказываем тропическую версию двойственной теоремы Гильберта о нулях и приводим для неё точные оценки (в классическом случае точные оценки для неё были получены Галлиго­Хайнцем­Колларом). Отметим, что прямой аналог теоремы Гильберта о нулях в тропическом мире неверен, поэтому рассматривается двойственная форма.

Наконец, совместно с А.Давыдовым доказаны оценки на число компонент связности тропического предмногообразия., которые являются аналогом классических оценок Олейник­Петровского­Милнора­Тома для вещественных полуалгебраических множеств.


Pages