Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SETH LOWER BOUND:
Reports tagged with SETH lower bound:
TR25-188 | 20th November 2025
Klim Efremenko, Dmitry Itsykson

Strong ETH Holds for Bounded-Depth Resolution over Parities

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 ... more >>>




ISSN 1433-8092 | Imprint