2026-07-24T03:47:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25368 2026-03-19T13:04:07Z ddc:004 open_access

Supercritical Tradeoff Between Size and Depth for Resolution over Parities Itsykson, Dmitry Knop, Alexander lifting theorems resolution depth resolution over parities resolution width supercritical tradeoff Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res(⊕)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with the same hardness properties, but which additionally admits a resolution refutation of quasi-polynomial size. This establishes a supercritical tradeoff between size and depth for resolution over parities. The proof builds on the framework of Alekseev and Itsykson and relies on a lifting argument applied to the supercritical tradeoff between width and depth in resolution, proposed by Buss and Thapen (IPL 2026). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Itsykson and Alexander Knop 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.81 urn:nbn:de:0030-drops-253680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.81 eng https://creativecommons.org/licenses/by/4.0/legalcode