Seminars

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



О теоретико-групповом обобщении теоремы Морса и Хедлунда

Speaker: 
Светлана Пузынина (Институт Математики им. Л. С. Соболева)
Date: 
Monday, October 31, 2016 - 14:00
Place: 
ПОМИ, ауд. 106
Abstract: 

В классической работе 1938 года Морс и Хедлунд доказали, что всякое непериодическое бесконечное слово содержит как минимум n+1 подслово длины n. Более того, бесконечное слово содержит ровно n+1 подслово для каждой длины n, если и только если оно бинарное, непериодическое и сбалансированное, т.е. является словом Штурма. В докладе мы рассмотрим обобщение понятия сложности слов через действия групп и обсудим обобщения теоремы Морса и Хедлунда.



Approximation and Parameterized Complexity of Minimax Approval Voting

Speaker: 
Krzysztof Sornat (University of Wroclaw)
Date: 
Monday, October 17, 2016 - 14:00
Place: 
ПОМИ, ауд. 106
Abstract: 

We present three results on the complexity of Minimax Approval Voting that is a voting rule for choosing committee of fixed size k. Here, we see the votes and the choice as 0-1 strings of length m (characteristic vertors of the subsets). The goal is to minimize the maximum Hamming distance to a vote. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2^o(d\log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d^(2d)) algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/eps)^(2d)), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time n^O(log(1/eps)/eps^2) * poly(m), almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].
Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat



An Information Complexity Approach to the KRW Composition Conjecture, часть 2

Speaker: 
Александр Смаль (ПОМИ)
Date: 
Monday, October 3, 2016 - 15:00
Place: 
ПОМИ, ауд. 402
Abstract: 

Мы продолжим изучать информационно-сложностной подход к нижней оценке на сложность KW(f o U_n)



Задача о наибольшей общей подпоследовательности: суперклей из водорослей

Speaker: 
Александр Тискин (University of Warwick)
Date: 
Friday, September 30, 2016 - 17:30
Place: 
ПОМИ, ауд. 203
Abstract: 

Вычисление наибольшей общей подпоследовательности (longest common subsequence, LCS) двух заданных строк - фундаментальная алгоритмическая задача, традиционно решаемая методом динамического программирования. Мы рассматриваем альтернативный метод решения типа divide-and-conquer, основанный на обобщении этой задачи, вычисляющем неявные матрицы полулокальных LCS. Решения на подзадачах "склеиваются" при помощи эффективного умножения в "моноиде водорослей", тесно связанном с классической группой кос. Предлагаемый метод позволяет получать эффективные алгоритмы для различных нетрадиционных вариантов задачи LCS - в частности, для LCS на динамических строках, сжатых строках, а также для параллельного вычисления LCS с минимальной коммуникацией и синхронизацией между процессорами.


Pages