Seminars

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



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

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-­полна.

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

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



Hub labeling

Speaker: 
Всеволод Опарин (ПОМИ РАН)
Date: 
Wednesday, August 5, 2015 - 18:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Посмотрим на задачу кратчайших путей в графе. Нам разрешается сделать
некоторый предподсчет, а потом нужно быстро отвечать на запросы, какое
расстояние между заданными вершинами. Можно посчитать матрицу
расстояний, но это потребует O(n^2) памяти. Для экономии памяти
используют метод Hub Labeling.

Для каждой вершины u выбирают некоторое множество хабов H_u, других
вершин графа, и до каждого хаба считают расстояние. Если у пары вершин
есть общий хаб на кратчайшем пути, то можно восстановить расстояние
между ними. Нужно расставить хабы так, чтобы между каждой парой вершин
можно было посчитать расстояние.

В задаче оптимизируют разные функции. Например в HL_1 минимизируют
суммарный размер хабов, в HL_inf минимизируют максимальный размер.

Результаты, которые хочу рассказать.
- log n приближение в общем случае
- log d приближение для случая уникальных путей, где d -- диаметр.
- log n неприближаемость HL_1
- log n неприближаемость HL_inf



Условные нижние оценки для задачи о гомоморфизме графов

Speaker: 
Иван Михайлин (ПОМИ РАН, UCSD)
Date: 
Tuesday, August 4, 2015 - 13:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

В задаче о гомоморфизме графов на вход подается два графа и требуется узнать, существует ли отображение вершин одного в вершины другого, которое переводит ребра в ребра. Задача о гомоморфизме графов обобщают задачу о раскраске графа, для которой не так давно был придуман относительно быстрый алгоритм со сложностью O*(2^n). За последние годы было предпринято несколько попыток адаптировать этот алгоритм (или придумать другой) для задачи о гомоморфизме, однако удовлетворительные результаты были получены только для частных случаев. В докладе будет показано, почему создание эффективного алгоритма для этой задачи противоречит ETH - популярной гипотезе о том, что для 3-SAT не существует алгоритма с субэкспоненциальным временем работы.


Pages