Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay · 2025
Read Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth by Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23008.txt.
Introduction
Sreejata Kishor Bhattacharya and Arkadev Chattopadhyay prove new lower bounds in 2025 for a proof system that mixes resolution with parity steps. For a deep class of such proofs, no strong size bounds were known before. Their hard case is a Tseitin formula on an expander graph, lifted with an inner product gadget.
Any proof in this system for the lifted formula must have huge size, as long as depth stays near quadratic in the variable count. A key step shows that lifted random inputs fool safe affine spaces. The result answers an open problem posed by prior work in the area.
Catalog record
| CREATOR | Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay Abstract Itsykson and Sokolov [ IS14 ] identified resolution over parities, denoted by Res ( ⊕ ) \text{Res}(\oplus) , as a natural and simple fragment of AC 0 [ 2 ] \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 [ EI25 ] proved lower bounds of the form exp ( N Ω ( 1 ) ) \text{exp}(N^{\Omega(1)}) , on the size of Res ( ⊕ ) \text{Res}(\oplus) proofs whose depth is upper bounded by O ( N log N ) O(N\log N) , where N N is the number of variables of the unsatisfiable CNF formula. The hard formula they used was Tseitin on an appropriately expanding graph, lifted by a 2 2 -stifling gadget. They posed the natural problem of proving super-polynomial lower bounds on the size of proofs that are Ω ( N 1 + ϵ ) \Omega(N^{1+\epsilon}) deep, for any constant ϵ > 0 \epsilon>0 . We provide a significant improvement by proving a lower bound on size of the form exp ( Ω ~ ( N ϵ ) ) \text{exp}(\tilde{\Omega}(N^{\epsilon})) , as long as the depth of the Res ( ⊕ ) \text{Res}(\oplus) proofs are O ( N 2 − ϵ ) O(N^{2-\epsilon}) , for every ϵ > 0 \epsilon>0 . Our hard formula is again Tseitin on an expander graph, albeit lifted with a different type of gadget. Our gadget needs to have small correlation with all parities. An important ingredient in our work is to show that arbitrary distributions lifted with such gadgets fool safe affine spaces, an idea which originates in the earlier work of Bhattacharya, Chattopadhyay and Dvorak [ BCD24 ] . 1 Introduction One of the simplest proof systems in propositional proof complexity is Resolution. Haken [ Hak85 ] obtained the first super-polynomial lower bounds on the size of proofs in this system for a CNF encoding of the pigeon-hole-principle forty years ago. Since then it has been very well studied with many beautiful results (see for example [ Urq87 ] , [ BW01 ] , [ ABRW04 ] ). Yet, seemingly slight strengthenings of resolution seem to frustrate current techniques in obtaining non-trivial lower bounds. We will consider one such strengthening, that was introduced by Itsykson and Sokolov [ IS14 ] , about ten years ago. This system is called resolution over parities, abbreviated by \text{Res}(\oplus) and denoted by \text{Res}(\oplus) . It augments resolution by allowing the prover to make \mathbb{F}_{2} -linear inferences, while working with \mathbb{F}_{2} -linear clauses. Proving superpolynomial lower bounds for \text{Res}(\oplus) remains a challenge. It is easy to see that \text{Res}(\oplus) is a subsystem of AC^{0}[2] -Frege. While we know strong lower bounds for AC^{0} -Frege (see for example [ BIK+92 ] ), obtaining super-polynomial lower bounds for AC^{0}[2] -Frege for any unsatisfiable formula in CNF would be a major breakthrough (see for example [ MP97 ] ). Thus, \text{Res}(\oplus) is in some sense the weakest natural subfragment of AC^{0}[2] -Frege for which we don’t currently have lower bounds. Proving lower bounds for \text{Res}(\oplus) would be a stepping stone towards proving lower bounds for AC^{0}[2] -Frege. Itsykson and Sokolov proved exponential lower bounds on the size of tree-like \text{Res}(\oplus) proofs using customized arguments for some formulas. General techniques for tree-like \text{Res}(\oplus) proofs were developed in the independent works of Beame and Koroth [ BK23 ] and Chattopadhyay, Mande, Sanyal and Sherif [ CMSS23 ] that lifted lower bounds on the height of ordinary tree-like resolution proofs of a formula to that of the size of tree-like \text{Res}(\oplus) proofs of the same formula lifted with an appropriate gadget. A more recent line of work ( [ EGI24 ] , [ BCD24 ] , [ AI25 ] , [ EI25 ] ) has focused on proving lower bounds against subsystems of \text{Res}(\oplus) that are stronger than tree-like but weaker than general \text{Res}(\oplus) . Gryaznov, Pudlak and Talebanfard [ GPT22 ] had proposed several notions of regular proofs for the \text{Res}(\oplus) system as appropriate first target for proving lower bounds. Efremenko, Garlik and Itsykson [ EGI24 ] established lower bounds against such a subsystem of \text{Res}(\oplus) known as bottom-regular \text{Res}(\oplus) . Bhattacharya, Chattopadhyay and Dvorak [ BCD24 ] exhibited a CNF which is easy for resolution but hard for bottom-regular \text{Res}(\oplus) - thereby strictly separating unrestricted \text{Res}(\oplus) from bottom-regular \text{Res}(\oplus) . Subsequently, Alekseev and Itsykson [ AI25 ] significantly extended the reach of techniques by showing \text{exp}(N^{\Omega(1)}) lower bounds against \text{Res}(\oplus) refutations whose depth is restricted to be at most O(N\log\log N) , where N is the number of variables of the unsatisfiable CNF. This depth restriction was further improved to O(N\log N) by Efremenko and Itsykson [ EI25 ] . A natural way towards proving lower bounds for unrestricted \text{Res}(\oplus) would be improving the depth restriction all the way to N^{\omega(1)} . However, the techniques of Efremenko and Itsykson [ EI25 ] seem to get stuck at O(N\log N) . Efremenko and Itsykson [ EI25 ] posed the natural open problem of proving superpolynomial lower bounds against \text{Res}(\oplus) refutations whose depth is restricted to O(N^{1+\epsilon}) where \epsilon>0 is some constant . Our main result, stated below, achieves such a bound. Theorem 1.1 . Let \Phi be the Tseitin contradiction on a (|V|,d,\lambda) expander with 0<\lambda<1 a small enough constant and |V| odd. Let n=|V|d/2 be the number of edges (which is also the number of variables in \Phi ). Let IP be the inner product gadget on b=500\log(n) bits. Let \Psi=\Phi\odot\text{IP} be the lift of \Phi by IP . Let N=nb be the number of variables in \Psi . Then, any \text{Res}(\oplus) refutation of \Psi of depth \leq O(N^{2-\epsilon}) requires size \exp(\tilde{\Omega}(N^{\epsilon})) This pushes the frontier of depth of proofs against which super-polynomial lower bounds on size for \text{Res}(\oplus) can be obtained, from O(N\log(N)) to \tilde{O}(N^{2}) . Another way of interpreting our result is to say that any \text{Res}(\oplus) proof of the hard formula \Psi of size \text{exp}(N^{o(1)}) has to be almost N^{2} deep, which is significantly super-critical. Our work combines the approaches of Alekseev and Itsykson [ AI25 ] , Efremenko and Itsykson [ EI25 ] and Bhattacharya, Chattopadhyay and Dvorak [ BCD24 ] - along with a new equidistribution lemma for safe affine spaces. 1.1 Some Other Related Work Our work makes use of the notion of amortized closure that was introduced by Efremenko and Itsykson [ EI25 ] . Apart from improving the depth lower bounds of small size \text{Res}(\oplus) proofs, [ EI25 ] used this notion to give an alternative proof of a lifting theorem of Chattopadhyay and Dvorák [ CD25 ] and their proof works for a broader class of gadgets. The lifting theorem is used in [ CD25 ] to prove super-criticial tradeoffs between depth and size of tree-like \text{Res}(\oplus) proofs. Our work also crucially uses lifted distributions to boost the success probability of random walks with restarts. In particular, it uses an analytic property of the gadget to argue equiditribution of pre-images in a