Seminars

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



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.



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.



Mathematics in Synchronization and Concurrency

Speaker: 
Пётр Кузнецов (Telecom ParisTech)
Date: 
Monday, December 22, 2014 - 18:00
Place: 
Аудитория 106, ПОМИ
Abstract: 

Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Therefore, understanding fundamentals of distributed computing is of crucial importance.

The main complication here is the immense diversity of applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. In this talk, we discuss understanding of what can and what cannot be implemented in specific distributed environments, with a focus on how to apply modern mathematics in deriving new algorithms and lower bounds for distributed computing problems.


Pages