Seminars

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


Пятница 25.10. Дмитрий Соколов: "(Semi)Algebraic proofs over $\{\pm 1\}$ variables"

Speaker: 
Дмитрий Соколов
Date: 
Friday, October 25, 2019 - 17:00
Place: 
ауд. 106
Abstract: 

In this talk, we study versions of Polynomial Calculus and Sum-of-Squares proof systems. Current techniques for size lower on these proof systems bounds significantly use {0, 1} encoding of variables. More formally, we need to be able to assign any variable by a feasible value in a way to kill a term, that helps us to reduce a question about size to a question about degree.

We know the for ``Fourier'' $\{\pm 1\}$ encoding of boolean variables degree lower bound is not enough to prove size lower bounds [Buss et al. 2001]. In this talk we present show exponential lower bounds on monomial size of proofs in SoS and PCR as well as separation between these systems. It is a solution to an open problem from [Impagliazzo, Mouli, Pitassi 2019].

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

Speaker: 
Д. Соколов (KTH)
Date: 
Wednesday, July 10, 2019 - 17:00
Place: 
203
Abstract: 

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

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"

Speaker: 
Navid Talebanfard (Institute of Mathematics CAS, Prague)
Date: 
Wednesday, July 10, 2019 - 12:00
Place: 
203
Abstract: 

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

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

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

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

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

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

Speaker: 
Виктор Лопаткин
Date: 
Friday, April 19, 2019 - 16:00
Place: 
ауд. 106
Abstract: 

В докладе будут представлены следующие две конструкции:
(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]$ с помощью этих конструкций. Наконец, мы вводим на множестве двудольных графов топологию Зарисского.

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

Pages