Supercritical Tradeoff Between Size and Depth for Resolution over Parities

Read full text
Authors: Dmitry Itsykson, Alexander Knop
Cited by: 1

Abstract

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).

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Polynomial and algebraic computation

Publication details

Journal / source
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
Publication date
1 January 2026
Language
EN