Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RESOLUTION DEPTH:
Reports tagged with resolution depth:
TR24-128 | 27th August 2024
Yaroslav Alekseev, Dmitry Itsykson

Lifting to regular resolution over parities via games

Revisions: 1

The propositional proof system resolution over parities (Res($\oplus$)) combines resolution and the linear algebra over GF(2). It is a challenging open question to prove a superpolynomial lower bound on the proof size in this system. For many years, superpolynomial lower bounds were known only in tree-like cases. Recently, Efremenko, Garlik, ... more >>>




ISSN 1433-8092 | Imprint