Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



Пятница 05.04. С.И. Грязнов: "Нижние оценки в древовидной системе доказательств Res(+) на ordering principles"

Докладчик: 
С.И. Грязнов
Дата: 
Friday, April 5, 2019 - 17:00
Место: 
ауд. 106
Аннотация: 

Система доказательств Res(+), предложенная Ицыксоном и Соколовым, -- расширение резолюционной системы доказательств. Она оперирует с дизъюнкциями линейных равенств над $F_2$. В докладе мы рассмотрим технику доказательства нижних оценок на размер доказательств некоторых противоречивых семейств формул для древовидной Res(+), основанную на играх Прувера и Дилеера. Данная техника является обобщением доказательства нижней оценки для принципа Дирихле. Затем мы применим данную технику для доказательства нижних оценок на Ordering principle и Dense Linear Ordering principle.

Ordering principle утверждает, что не существует конечного линейного порядка без минимума. Мы дадим нижнюю оценку $2^{n−O(1)}$ на размер любого древовидного Res(+) доказательства этого утверждения, записанного в КНФ. Dense Linear Ordering principle утверждает, что не существует конечных плотных линейных порядков. Мы дадим $2^{n/3−O(1)}$ нижнюю оценку на размер любого древовидного Res(+) доказательства этого утверждения, записанного в КНФ.

Ordering principle и Dense Linear Ordering principle имеют доказательство полиномиального размера в резолюциях. Таким образом, мы приведем естественные примеры, разделяющие древовидную версию системы Res(+) и резолюцию.



Пятница 29.03. Д.М. Ицыксон (ПОМИ РАН): "Нижние оценки для OBDD-систем доказательств, использующих несколько порядков на переменных"

Докладчик: 
Д.М. Ицыксон (ПОМИ РАН)
Дата: 
Friday, March 29, 2019 - 17:00
Место: 
ауд. 106
Аннотация: 

Упорядоченные диаграммы принятия решений (OBDD) - это частный случай однопроходных ветвящихся программ, в которых переменные встречаются в определенном порядке. Наложенное ограничение позволяет эффективно выполнять многие операции с булевыми функциями, записанными в этом виде. В 2004 году Атсериас, Варди и Колайтис предложили систему доказательств, в которых строки доказательств записываются в виде OBDD, из двух OBDD можно выводить любую OBDD, которая из них семантически следует. В 2008 году Крайчек доказал экспоненциальную нижнюю оценку в этой системе доказательств, если все OBDD в доказательстве используют одни и те же порядки на переменных. Если разрешить использовать в доказательствах OBDD в разных порядках, то получится строго более сильная система доказательств, для которой суперполиномиальных нижних оценок не известно.

В докладе мы рассмотрим исчисление однопроходных ветвящихся программ (1-BP), в котором можно выводить новые 1-BP как конъюнкцию уже имеющихся или как проекцию имеющейся 1-BP. Это семантическое обобщение некоторой подсистемы упомянутой выше OBDD-системы доказательств, в которой можно использовать различные порядки на переменных в OBDD. Мы покажем, что существует семейство невыполнимых формул $F_n$ в O(1)-КНФ и константа C, что любой вывод в этом исчислении, использующий проекции по не более, чем Cn различным переменным, имеет размер хотя бы $2^{\Omega(n)}$.

Доклад основан на совместной работе с С. Басом, А. Кнопом, А. Рязановым и Д. Соколовым.



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

Докладчик: 
Евгений Стратоников
Дата: 
Friday, December 14, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 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"

Докладчик: 
Кирилл Симонов (Университет Бергена)
Дата: 
Tuesday, December 11, 2018 - 02:00
Место: 
ауд. 106
Аннотация: 

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, ИППИ РАН): "Три подхода к определению понятия количества информации: увеличение сложности при случайном шуме"

Докладчик: 
А.Х. Шень (LIRMM, ИППИ РАН)
Дата: 
Monday, December 10, 2018 - 14:30
Место: 
106
Аннотация: 

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

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


Pages