Семинары

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



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

Докладчик: 
Татьяна Белова
Дата: 
Friday, November 30, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

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



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

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

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



Понедельник 19.11. Федор Парт: "Нижние оценки для резолюций с линейными уравнениями над кольцами"

Докладчик: 
Федор Парт
Дата: 
Monday, November 19, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

Система доказательств Res($lin_R$) определяется как расширение резолюционной системы доказательств Res, в ней выводимыми утверждениями являются дизъюнкции линейных уравнений над кольцом R. Одна из мотиваций для изучения таких систем заключается в том, что если R - это конечное поле $F_p$ или поле рациональных чисел, то Res(lin_R) является простейшим примером систем $AC_0[p]$-Frege или $TC_0$-Frege соответственно, доказательство суперполиномиальных нижних оценок на длины доказательств в которых - давно открытая проблема. Оказывается, даже для Res($lin_R$) проблема доказательства нижних оценок в общем случае крайне нетривиальна и на данный момент является открытой.

В докладе мы докажем ряд dag-like и tree-like верхних и нижних оценок на размер доказательств в Res($lin_F$) для разных полей F. В случае char(F)=0 мы докажем экпоненциальную нижнюю оценку, но не для КНФ, а для клоза вида $a_1x_1+...+a_nx_n=A$ для больших, то есть растущих суперполиномиально от n, коэффициентов. Эта оценка получается как следствие из полиномиальных нижних и верхних оценок на размер кратчайшего Res($lin_F$) доказательства как функции от размера образа линейной формы $a_1x_1+...+a_nx_n$. Также в случае char(F)=0 мы докажем экспоненциальную tree-like нижнюю оценку на $a_1x_1+...+a_nx_n=A$, если коэффициенты малы, то есть ограничены полиномом от n. Это влечет экспоненциальное разделение dag-like и tree-like Res(lin_F) в случае малых коэффициентов

Для конечных полей мы докажем экспоненциальные разделения между tree-like Res(lin_Fp) и tree-like Res(lin_Fq) для различных p и q, где в качестве разделяющих КНФ использованы mod-p Цейтинские формулы. Этот результат, а также экспоненциальная нижняя оценка для tree-like Res(lin_Fp) на случайных КНФ, получается как следствие варианта классического соотношения ширины и размера резолюционных доказательств вкупе с нижней оценкой на ширину через симуляцию в Polynomial Calculus. Мы обобщим доказательство Ицыксона и Соколова tree-like Res($lin_{F_2}$) нижней оценки на PHP для произольных полей F с помощью теоремы Алона-Фюреди о покрытиях гиперкуба гиперплоскостями.

Доклад основан на совместной статье с И. Цамеретом.



Пятница 16.11. Людмила Глинских: "Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors"

Докладчик: 
Людмила Глинских
Дата: 
Friday, November 16, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

Мы рассмотрим задачу Orthogonal Vectors, в которой дано множество из n d-мерных булевых векторов и необходимо определить, есть ли среди этого множества два вектора ортогональных друг другу. Существует гипотеза (Orthogonal Vector Conjecture, OVC), что при d порядка log(n) любой алгоритм для данной задачи работает за время $n^{2-o(1)}$. В предположении данной гипотезы уже доказаны нижние оценки для многих других задач из класса P, например, для задач Edit Distance и Longest Common Subsequence.

Мы покажем, что OVC верна в некоторых вычислительных моделях, а именно для вычисления OV требуется формула (с любым базисом, с константной входящей степенью в вершинах) и ветвящаяся программа квадратичного размера. Данная нижняя оценка совпадает с лучшими известными нижними оценками для явных функций в данных моделях.

Доклад по статье The Orthogonal Vectors Conjecture for Branching Programs and Formulas авторов Daniel Kane и Ryan Williams.



Пятница 09.11. В.В. Подольский (ВШЭ): "Нижние оценки в модели разрешающих деревьев с XOR-запросами"

Докладчик: 
В.В. Подольский (ВШЭ)
Дата: 
Friday, November 9, 2018 - 14:00
Место: 
106
Аннотация: 

В докладе будет рассказано о новой оценке на сложность D(f) вычисления булевых функций в модели разрешающих деревьев с XOR запросами . В этой модели требуется вычислить известную булеву функцию f на неизвестном входе. За один запрос разрешается узнать XOR любого подмножества входных битов. Мерой сложности является число запросов в худшем случае.

Гранулярностью gran(f) булевой функции f называется минимальное натуральное k, такое что всякий коэффициент Фурье функции f выражается как целое число, умноженное на 1/2^k. Мы докажем, что D(f) ≥ gran(f)+1. Эта нижняя оценка является усилением оценок на D(f) через l_0-норму спектра Фурье f и через степень f как многочлена над GF(2). Используя новую оценку мы находим точное значение D(f) для некоторых важных функций f, включая функцию голосования и итерированную функцию голосования. Для функции голосования сложность оказывается равной n-B(n)+1, где B(n) равно числу единиц в двоичной записи n. Для итерированной функции голосования сложность равна (n+1)/2. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.


Pages