Семинары

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



Пятница 26.04. Андрей Рыжиков (университет Пари-Эст Марн-ля-Вале, Франция): "О поиске коротких синхронизирующих слов для префиксных кодов"

Докладчик: 
Андрей Рыжиков (университет Пари-Эст Марн-ля-Вале, Франция)
Дата: 
Friday, April 26, 2019 - 17:00
Место: 
ауд. 106
Аннотация: 

Префиксные коды -- это наиболее известный класс кодов переменной длины, широко используемый при сжатии и передаче информации. В общем случае коды переменной длины неустойчивы к ошибкам, так как одно удаление, добавление или замена символа способны десинхронизировать декодер, тем самым сделав весь дальнейший процесс декодирования некорректным. Тем не менее, для широкого класса кодов (называемых синхронизируемыми) возможно возвращение к корректному декодированию.

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

Это совместная работа с Мареком Шикуа (университет Вроцлава, Польша), являющаяся усилением наших результатов с MFCS 2018.



Пятница 19.04. Виктор Лопаткин: "Двудольные графы как полиномы и полиномы как двудольные графы"

Докладчик: 
Виктор Лопаткин
Дата: 
Friday, April 19, 2019 - 16:00
Место: 
ауд. 106
Аннотация: 

В докладе будут представлены следующие две конструкции:
(1) По каждому неориентированному (ориентированному) конечному двудольному графу $\Gamma = (V,U,E)$ строится полином $p(\Gamma)$, который в случае, если граф $\Gamma$ неориентируемый, то $p\in \mathbb{N}[x]$, а если $\Gamma$ -- ориентируемый, то $p(\Gamma) \in \mathbb{N}[x,y]$.
(2) По каждому полиному $p\in \mathbb{N}[x]$ строится неоринтируемый двудольный конечный граф $\Gamma(p)$, а по каждому полиному $p\in\mathbb{N}[x,y]$ строится ориентируемый конечный двудольный граф $\Gamma(p)$.

При этом, обе эти конструкции взаимно обратны друг к другу, то есть $\Gamma(p(\Gamma)) = \Gamma$. Мы далее покажем, что обычное произведение (двудольных) графов $\Gamma_1\times \Gamma_2$ соответствует произведению их полиномов, то есть $\Gamma_1 \times \Gamma_2 = \Gamma(p(\Gamma_1)\cdot p(\Gamma_2))$, а граф соответствующий сумме полиномов, скажем $p_1+p_2$, есть граф полученный ``приклеиванием'' графа $\Gamma(p_1)$ к $\Gamma(p_2)$ по определённому, но при этом простому, правилу.

Как приложение, мы обсудим делимость в полукольцах $\mathbb{N}[x]$, $\mathbb{N}[x,y]$ с помощью этих конструкций. Наконец, мы вводим на множестве двудольных графов топологию Зарисского.

Доклад по совместной работе с Андреем Гринблат.



Среда 17.04. Д. Соколов: "Псевдо-ширина и замыкания"

Докладчик: 
Д. Соколов
Дата: 
Wednesday, April 17, 2019 - 14:00
Место: 
1006
Аннотация: 

Резолюция является наиболее хорошо изученной системой доказательств. Известные техники для доказательств нижних оценок на данную систему плохо применимы в случае, когда формула <<перегружена>> переменными. Одним из ярких примеров <<нехорошей>> для резолюций формулы является Weak-PigeonHole (принцип Дирихле с m кроликами и n клетками, причем m >> n^2). Впервые нижняя оценка для данной формулы была доказана Разом в 2001 году, Разборов впоследствии усилил и обобщил с помощью своего так называемого метода псевдоширины.

На семинаре мы обсудим технику псевдо-ширины, и покажем нижнюю оценку на weak-PHP для разреженных графов. Совместная работа с Susanna F. de Rezende, Jakob Nordström и Kilian Risse.



Пятница 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)}$.

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


Pages