[Proof Complexity] new preprint
Dmitry Itsykson
dmitrits at gmail.com
Thu Oct 24 12:48:51 CEST 2024
Dear colleagues,
We've posted a new revision of our ECCC preprint,
Yaroslav Alexeev and Dmitry Itsykson "Lifting to bounded-depth and regular
resolutions over parities via games";
it is available at
https://eccc.weizmann.ac.il/report/2024/128/revision/1/download
In this revision, we added the new result, an exponential lower bound for
Res(⊕) with depth bounded by c n log log n, where n is the number of
variables in the refuted formula, and c is a constant. This fragment of Res(
⊕) covers all reasonable definitions of regularity.
Any comments or corrections are highly appreciated.
Best regards,
Dmitry.
More information about the Proof-Complexity
mailing list