[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