Seminars

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



Пятница 14.12. Евгений Стратоников: "Коммуникационная сложность и нижние оценки на размер ветвящихся программ"

Speaker: 
Евгений Стратоников
Date: 
Friday, December 14, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 2 множества $X\cup Y = M$. Мы рассмотрим естественное обобщение, в котором протокол может недетерминированно выбирать между $k$ различными подпротоколами, каждый из которых использует разное разбиение $f_1(X_1, Y_1)$, ... $f_k(X_k, Y_k)$, определим multi-partition communication complexity, и изучим её связь с нижними оценками на сложность однопроходных ветвящихся программ. Если останется время, приведем пример семейства задач, сложность которых уменьшается при переходе от протокола с $k$ разбиениями, к протоколу с $k+1$ разбиением.

Доклад по статье P. Duris, J. Hromkovic, Juraj, S. Jukna, M. Sauerhoff, G. Schnitger, On Multi-Partition Communication Complexity.



Вторник 11.12. Кирилл Симонов (Университет Бергена): "Параметризованная сложность задачи k-means"

Speaker: 
Кирилл Симонов (Университет Бергена)
Date: 
Tuesday, December 11, 2018 - 02:00
Place: 
ауд. 106
Abstract: 

k-means кластеризация -- это следующая задача: по данным n точкам в $R^d$ найти k центров кластеров так, чтобы минимизировать сумму расстояний от точек до ближайших к ним центрам кластеров. Задача получила широкую известность благодаря применениям в data mining, и в особенности эвристическому алгоритму Ллойда. Известно, что найти
оптимальную кластеризацию NP-трудно даже при d=2 или k=2, в то же время существует алгоритм со временем работы $n^{O(dk)}$. Мы впервые рассматриваем задачу k-means с точки зрения параметризованной сложности, где целью является либо нахождение алгоритма со временем
работы $f(t)n^{O(1)}$ для некоторого параметра задачи t, либо доказательство невозможности его существования при условии FPT≠W[1]. Рассматриваемые нами параметры для k-means -- это k, d и искомое расстояние D (при условии, что входные данные целочисленные).

Используя алгоритм для быстрого нахождения подгиперграфа с малым fractional cover number, мы получаем FPT-алгоритм по D для $L_1$-расстояния. Интересно, что в случае расстояния в $L_2$ задача ощутимо труднее — мы показываем, что одна из подзадач, возникающая в нашем алгоритме, является здесь W[1]-трудной. Мы также обобщаем эти результаты на $L_p$ для остальных значений p, и даем нижние оценки для некоторых комбинаций параметров в экстремальных случаях $L_0$ and $L_\infty$. Отдельный интерес может представлять набор используемых нами сведений, позволяющих представить стандартные комбинаторные задачи на графах как геометрические задачи кластеризации.



Понедельник 10.12. А.Х. Шень (LIRMM, ИППИ РАН): "Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме"

Speaker: 
А.Х. Шень (LIRMM, ИППИ РАН)
Date: 
Monday, December 10, 2018 - 14:30
Place: 
106
Abstract: 

Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов. Мы делаем то же самое в вероятностной ситуации и выясняем, какова может быть типичная сложность данного слова $x$, если в нём каждый бит изменить с вероятностью $p$, получая неулучшаемую оценку для этой типичной сложности.

(по работе с Глебом Пособиным)



Пятница 30.11. Татьяна Белова: "Верхние и нижние оценки для различных параметризаций задачи (n, 3)-MAXSAT"

Speaker: 
Татьяна Белова
Date: 
Friday, November 30, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

Задача (n,3)-MAX-SAT является частным случаем задачи MAX-SAT с дополнительным ограничением на входную формулу, что каждая переменная встречается в формуле не более трех раз. Мы рассмотрим различные параметризации этой задачи, улучшим известные ранее верхние оценки на время решения (n,3)-MAXSAT относительно числа переменных в формуле, а также относительно числа клозов, которые мы хотим выполнить.
Кроме того, мы покажем, что выполнить хотя бы на один клоз больше, чем при тривиальном означивании, где всем переменным присваивается истина, уже является NP-трудной задачей.



Пятница 23.11. Анастасия Софронова: "Верхние оценки на размер dag-like коммуникационных протоколов"

Speaker: 
Анастасия Софронова
Date: 
Friday, November 23, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

Dag-like коммуникационные протоколы — обобщение классических коммуникационных протоколов. С их помощью можно перенести нижние оценки на ширину резолюционного доказательства невыполнимой формулы на другие системы доказательств, а также на размер монотонных схем для некоторых связанных задач. Для этого используется техника lifting — вместо каждой переменной формулы подставляется некоторая функция от новых переменных, так называемый гаджет. Однако известные гаджеты, подходящие для этой техники, имеют большой размер. Вопрос, можно ли использовать гаджет константного размера, является открытым. Мы рассмотрим некоторые конкретные гаджеты константного размера и приведём пример семейства формул, показывающий, что их нельзя использовать для переноса нижних оценок. А именно, рассмотрим семейство формул с минимальной шириной резолюционного доказательств $\Omega(\sqrt{n})$ и полиномиальным размером dag-like протокола для задачи поиска невыполненного дизъюнкта после подстановки гаджета.


Pages