Seminars

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



Среда 22.04. В.В. Подольский (МИАН, НИУ ВШЭ): "Вычисление функций голосования монотонными формулами маленькой глубины"

Speaker: 
В.В. Подольский (МИАН, НИУ ВШЭ)
Date: 
Wednesday, April 22, 2020 - 18:10
Place: 
Zoom meeting
Abstract: 

Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.

Доклад основан на совместной работе с Александром Козачинским: https://eccc.weizmann.ac.il/report/2020/017/

Доклад пройдет в Zoom, необходима регистрация. Для регистрации пройдите по ссылке.
https://zoom.us/meeting/register/tJcucemuqD0oGtLqf7hoIiurxtIqW9P_QRs-
После регистрации вы получите подтверждение по почте с информацией о докладе.



Пятница 27.12. Дмитрий Соколов: "Trade-offs Between Size and Degree in Polynomial Calculus"

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

Building on [Clegg et al.~'96], [Impagliazzo et al.~'99] established that if an unsatisfiable $k$-CNF formula over $n$~variables has a refutation of size~$S$ in the polynomial calculus resolution proof system, then this formula also has a refutation of degree $k + O(\sqrt{n \log S})$. The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen~'16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.



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


Pages