Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-188 | 20th November 2025 18:21

Strong ETH Holds for Bounded-Depth Resolution over Parities

RSS-Feed




TR25-188
Authors: Klim Efremenko, Dmitry Itsykson
Publication: 21st November 2025 15:46
Downloads: 29
Keywords: 


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. We additionally provide a direct and simplified proof for this special case, which may be of independent interest.



ISSN 1433-8092 | Imprint