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-039 | 31st March 2025 12:11

Amortized Closure and Its Applications in Lifting for Resolution over Parities

RSS-Feed




TR25-039
Authors: Klim Efremenko, Dmitry Itsykson
Publication: 6th April 2025 05:07
Downloads: 98
Keywords: 


Abstract:

The notion of closure of a set of linear forms, first introduced by Efremenko, Garlik, and Itsykson [EGI-STOC-24], has proven instrumental in proving lower bounds on the sizes of regular and bounded-depth Res($\oplus)$ refutations [EGI-STOC-24, AI-STOC-25]. In this work, we present amortized closure, an enhancement that retains the properties of original closure [EGI-STOC-24] but offers tighter control on its growth. Specifically, adding a new linear form increases the amortized closure by at most one. We explore two applications that highlight the power of this new concept.

Utilizing our newly defined amortized closure, we extend and provide a succinct and elegant proof of the recent lifting theorem by Chattopadhyay and Dvorak [CD-ECCC-2024]. Namely we show that for an unsatisfiable CNF formula $\varphi$ and a 1-stifling gadget $g\colon\{0,1\}^\ell\to \{0,1\}$, if the lifted formula $\varphi \circ g$ has a tree-like $\resoplus$ refutation of size $2^d$ and width $w$, then $\varphi$ has a resolution refutation of depth $d$ and width $w$. The original theorem by Chattopadhyay and Dvorak [CD-ECCC-2024] applies only to the more restrictive class of strongly stifling gadgets.

We further utilize amortized closure to show improved lower bounds for bounded-depth Res($\oplus$), extending the depth beyond that of Alekseev and Itsykson [AI-STOC-25]. Our result establishes an exponential lower bound for depth-$\Omega(n \log n)$ Res($\oplus$) refutations of lifted Tseitin formulas, a notable improvement over the existing depth-$\Omega(n \log \log n)$ Res($\oplus$) lower bound.



ISSN 1433-8092 | Imprint