We show that for any unsatisfiable CNF formula φ that requires resolution refutation width at least w, and for any 1-stifling gadget g (for example, g = MAJ₃), (1) every resolution-over-parities (Res(⊕)) refutation of the lifted formula φ∘g of size at most S has depth at least Ω(w²/log S); (2) every Res(⊕) refutation of the lifted formula φ∘g has size Ω(w²). The first result substantially extends and simplifies all previously known lifting theorems for bounded-depth Res(⊕). The lifting result of Itsykson and Knop [Dmitry Itsykson and Alexander Knop, 2026] requires gadgets of logarithmic size and applies only to refutations of depth at most O(nlog n), whereas our result applies to nearly quadratic depth. The liftings of Bhattacharya and Chattopadhyay [Sreejata Kishor Bhattacharya and Arkadev Chattopadhyay, 2025] and of Byramji and Impagliazzo [Farzan Byramji and Russell Impagliazzo, 2025] apply to nearly quadratic depth as well, but rely on a much stronger assumption of (Ω(n),Ω(n))-DT-hardness, which is far less standard than large resolution width. Our proof combines the random-walk-with-restarts method of Alekseev and Itsykson [Yaroslav Alekseev and Dmitry Itsykson, 2025] with a new idea: the random walk is defined relative to the structure of the refutation graph, rather than by a distribution on inputs induced by the formula. Using this technique, we substantially strengthen the supercritical size-depth tradeoff of Itsykson and Knop [Dmitry Itsykson and Alexander Knop, 2026], both by improving the depth lower bound and by reducing the size of the separating formulas to polynomial in the number of variables, with the latter resolving an open question posed in [Dmitry Itsykson and Alexander Knop, 2026]. In particular, we construct a family of polynomial-size formulas that admit polynomial-size resolution refutations, while any Res(⊕) refutation of depth o(n²/log⁴ n) necessarily has superpolynomial size. Our second result yields a pure quadratic lower bound on the size of Res(⊕) refutations, improving upon the previously known near-quadratic lower bound of [Farzan Byramji and Russell Impagliazzo, 2025].

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [Paul Beame and Sajin Koroth, 2023] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that for any m ≥ 4 deterministic decision tree complexity of a function f can be lifted to the so called semi-structured communication complexity of f∘Ind_m, where Ind_m is the Indexing gadget. As our main contribution we extend these results to randomized setting. Our results also apply to a substantially larger set of gadgets. More specifically, we introduce a new complexity measure of gadgets, linear diversity. For all gadgets g with non-trivial linear diversity we show that randomized decision tree complexity of f lifts to randomized semi-structured communication complexity of f∘g. In particular, this gives tight lifting results for Indexing gadget Ind_m, Inner Product gadget IP_m for all m ≥ 2, and for Majority gadget MAJ_m for all m ≥ 4. We prove the same results for deterministic case. From our result it immediately follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [Arkadev Chattopadhyay et al., 2023] for Inner Product gadget. To obtain our results we introduce a new secret sets approach to simulation of semi-structured communication protocols by decision trees. It allows us to simulate (restricted classes of) communication protocols on truly uniform distribution of inputs.