Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-132 | 6th September 2024 21:36

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

RSS-Feed




TR24-132
Authors: Arkadev Chattopadhyay, Pavel Dvorak
Publication: 6th September 2024 21:57
Downloads: 100
Keywords: 


Abstract:

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 Resolution over parities, commonly denoted by $\text{Res}(\oplus)$, with parameters essentially unchanged.

To obtain our result, we extend the lifting theorem of Chattopadhyay, Mande, Sanyal and Sherif [ITCS, 2023] to handle tree-like affine DAGs. We introduce additional ideas from linear algebra to handle forget nodes along long paths.



ISSN 1433-8092 | Imprint