Mathematical Logic and Discrete Mathematics at PDMI

Четверг, 24 сентября, Zoom. Начало в 14:00.

Докладчик: Д.М. Ицыксон (ПОМИ).

Тема: Strong ETH Holds for Bounded-Depth Resolution over Parities.

Abstract

Strong lower bounds of the form $2^{(1-\epsilon)n}$, where $n$ is the
number of variables and $\epsilon>0$ is arbitrarily small (i.e.,
bounds consistent with the Strong ETH), are exceptionally rare in
proof complexity. The seminal work of Beck and Impagliazzo (STOC 2013)
achieved such a bound for regular resolution, and the strongest
extension known prior to our work was proved for $O(\epsilon)$-regular
resolution by Bonacina and Talebanfard (Algorithmica, 2017).

We establish similar lower bounds for a significantly stronger proof
system~--- a fragment of resolution over parities (Res($\oplus$)).
This fragment captures Depth-$n$ Res($\oplus$), and thus our result
implies SETH-type lower bounds for both tree-like and regular
Res($\oplus$). The core of our approach is a lossless lifting achieved
by assigning distinct, randomly chosen gadgets to each variable.

Our result also yields a SETH-type lower bound for Depth-$n$
resolution~--- a result that was previously unknown. In the talk, I
present a direct and simplified proof for this special case, which may
be of independent interest.

Based on joint work with Klim Efremenko.