Razborov [J. ACM, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter $k = k(n)$, there exists $k$-CNF formulas over $n$ variables, having resolution refutations of $O(k)$ width, but every tree-like refutation of width $n^{1-\epsilon}/k$ needs size $\text{exp}\big(n^{\Omega(k)}\big)$. We extend this result to tree-like ... more >>>

The notion of closure of a set of linear forms, first introduced by Efremenko, Garlik, and Itsykson [EGI-STOC-24], has proven instrumental in proving lower bounds on the sizes of regular and bounded-depth Res($\oplus)$ refutations [EGI-STOC-24, AI-STOC-25]. In this work, we present amortized closure, an enhancement that retains the properties of ... more >>>

Itsykson and Sokolov identified resolution over parities, denoted by $\text{Res}(\oplus)$, as a natural and simple fragment of $\text{AC}^0[2]$-Frege for which no super-polynomial lower bounds on size of proofs are known. Building on a recent line of work, Efremenko and Itsykson proved lower bounds of the form $\text{exp}(N^{\Omega(1)})$, on the size ... more >>>

Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res($\oplus$)) 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 ... more >>>

We prove that for the bit pigeonhole principle with any number of pigeons and $n$ holes, any depth $D$ proof in resolution over parities must have size $\exp(\Omega(n^3/D^2))$. Our proof uses the random walk with restarts approach of Alekseev and Itsykson [STOC '25], along with ideas from recent simulation theorems ... more >>>