Seminars

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


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

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 не существует алгоритма с субэкспоненциальным временем работы.

Прокалывающие окружности, двойственность и обобщенные диаграммы Вороного

Speaker: 
Елена Храмцова (University of Lugano (USI), Switzerland)
Date: 
Tuesday, July 21, 2015 - 13:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Цель вычислительной геометрии — создание алгоритмов, эффективно отвечающих на вопросы, возникающие в прикладных областях, которые манипулируют дискретными геометрическими объектами. Один из таких вопросов — вопрос о фигуре определенного типа, которая прокалывает (stabs) множество простых объектов. Например, определить, есть ли для данного множества из n отрезков на плоскости прямая, прокалывающая их все, можно за время O(n log n) c использованием двойственного преобразования на плоскости.[2] Если мы спросим о прокалывающей окружности (вместо прямой), элегантный результат из учебника превратится в открытую задачу. Используя другой тип двойственного преобразования, мы показали связь этой проблемы и обобщенных диаграмм Вороного (диаграммы Вороного в Хаусдорфовой метрике (Hausdorff Voronoi diagram) и диаграммы Вороного дальнего цвета (farthest-color Voronoi diagram).[1] Специальные свойства этих диаграмм позволили нам создать новый алгоритм для решения задач о прокалывающей окружности. Временная сложность решения данных задач понизилась сO(n^2) до O(n log^2 n) в случае если все отрезки множества колинеарны. В случае произвольных отрезков, наш метод понизил сложность с O(n^2 log^2 n) до O(n^2).

Основано на:
[1] M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, C. Seara, Stabbing circles for sets of segments in the plane. XVI EGC, Barcelona, 2015
[2] H. Edelsbrunner, L.J. Guibas, M. Sharir, The upper envelope of piecewise linear functions: algorithms and applications, Discrete Comput. Geom. 4 (1989), 311– 336.

Based on paper: 
M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, C. Seara, Stabbing circles for sets of segments in the plane. EGC 2015

Hierarchies against Sublinear Advice

Speaker: 
Александр Смаль (ПОМИ РАН)
Date: 
Monday, January 26, 2015 - 17:00
Place: 
Аудитория 402
Abstract: 

We strengthen the non-deterministic time hierarchy theorem to show that the lower bound holds against sublinear advice. More formally, we show that for any constants c and d such that 0 < c < d, there is a language in NTIME(n^d) which is not in NTIME(n^c)/n^{1/d}. The best known earlier separation could only handle o(log(n)) bits of advice in the lower bound. We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almost-everywhere hierarchy theorem for non-deterministic classes which use a sublinear amount of non-determinism, i.e., the lower bound holds on all but finitely many input lengths rather than just on in finitely many. As an application of our main result, we derive a new lower bound for NP against NP-uniform non-deterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k.

Based on paper: 
L. Fortnow, R. Santhanam. Hierarchies Against Sublinear Advice. ECCC report TR14-171. 2014

Pages