Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOM WALK WITH RESTARTS:
Reports tagged with Random Walk with Restarts:
TR26-018 | 12th February 2026
Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov

Resolution Width Lifts to Near-Quadratic-Depth Res($\oplus$) Size

We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every resolution-over-parities (Res($\oplus$)) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) ... more >>>




ISSN 1433-8092 | Imprint