Семинары

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



Среда 10.07. Д. Соколов (KTH): "A proof of the Sensitivity Conjecture & A tradeoff between length and width in PCR"

Докладчик: 
Д. Соколов (KTH)
Дата: 
Wednesday, July 10, 2019 - 17:00
Место: 
203
Аннотация: 

Докладчиком предлагается рассмотреть две темы. Распределение времени семинара между темами будет определяться пожеланиями слушателей семинара.

Title: A proof of the Sensitivity Conjecture

In this talk we will show that for any function f block sensitivity of f is bounded by a polynomial of sensitivity of f.

Based on paper of Hao Huang: "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture".

Title: A tradeoff between length and width in PCR

For various proof systems we know that proof of small size can be translated into a proof of small degree (or small width). In this constructions, the size of the final proof is usually exponential in terms of variables of the formula. For Resolution Thapen showed that it is necessary. We extend his result into polynomial calculus proof system.

More formally:
We construct a formula \varphi of size n that in polynomial calculus resolution (PCR) has a refutation of polynomial size and degree c := n^{1 - o(1)} and hence a refutation of exponential size and degree n^{0.5 + o(1)}. However, we show that there is no refutation achieving both polynomial size and degree at most c - O(\lg n)$ at the same time.

Joint work with Guillaume Lagarde, Jakob Nordström, Joseph Swernofsky.



Среда 10.07. Navid Talebanfard (Institute of Mathematics CAS, Prague): "A separator theorem for hypergraphs and a CSP-SAT algorithm"

Докладчик: 
Navid Talebanfard (Institute of Mathematics CAS, Prague)
Дата: 
Wednesday, July 10, 2019 - 12:00
Место: 
203
Аннотация: 

I will show how to remove a small number of edges from a hypergraph of small degree to break it into small connected components. I will then use it to solve CSP-SAT instances in which no variable appears in too many constraints and to give refutations of Tseitin formulas in small degree graphs with savings independent of the degree.

Joint work with Michal Koucký and Vojtěch Rödl.



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


Pages