Seminars

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



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 с минимальной коммуникацией и синхронизацией между процессорами.



Monotone real circuit

Speaker: 
Дмитрий Соколов (ПОМИ)
Date: 
Friday, September 30, 2016 - 14:00
Place: 
ПОМИ, ауд. 402
Abstract: 

В докладе рассмотрим доказательство нижних оценок на монотонные вещественные схемы для функции Broken Mosquito Screen. Доказательство основано на построениие заборов и идейно отличается от доказательства Разборова для Clique-Coloring.
Также мы докажем нижнюю оценку на Cutting Plane не ссылаясь на доказательство Пудлака.



An Information Complexity Approach to the KRW Composition Conjecture

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

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $ P \not \subset NC^1 $). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds.

Karchmer, Raz, and Wigderson [KRW95] suggested to approach this problem by proving the following conjecture: given two Boolean functions $ f $ and $ g $, the depth complexity of the composed function gf is roughly the sum of the depth complexities of $ f $ and $ g $. They showed that the validity of this conjecture would imply that $ P \not \subset NC^1 $.

As a starting point for studying the composition of functions, they introduced a relation called "the universal relation", and suggested to study the composition of universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Håstad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation.


Pages