Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BINARY PIGEONHOLE PRINCIPLE:
Reports tagged with binary pigeonhole principle:
TR23-187 | 27th November 2023
Klim Efremenko, Michal Garlik, Dmitry Itsykson

Lower bounds for regular resolution over parities

Revisions: 2

The proof system resolution over parities (Res($\oplus$)) operates with disjunctions of linear equations (linear clauses) over $\mathbb{F}_2$; it extends the resolution proof system by incorporating linear algebra over $\mathbb{F}_2$. Over the years, several exponential lower bounds on the size of tree-like Res($\oplus$) refutations have been established. However, proving a superpolynomial ... more >>>




ISSN 1433-8092 | Imprint