Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RESOLUTION OVER PARITIES:
Reports tagged with Resolution over parities:
TR24-132 | 6th September 2024
Arkadev Chattopadhyay, Pavel Dvorak

Super-critical Trade-offs in Resolution over Parities Via Lifting

Revisions: 1

Razborov [J. ACM, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter $k = k(n)$, there exists $k$-CNF formulas over $n$ variables, having resolution refutations of $O(k)$ width, but every tree-like refutation of width $n^{1-\epsilon}/k$ needs size $\text{exp}\big(n^{\Omega(k)}\big)$. We extend this result to tree-like ... more >>>


TR25-039 | 31st March 2025
Klim Efremenko, Dmitry Itsykson

Amortized Closure and Its Applications in Lifting for Resolution over Parities

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




ISSN 1433-8092 | Imprint