PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds

Xin Li, Yan Zhong

arXiv:2610.02407v1cs.CCmath.AGmath.CO

TL;DR

The paper addresses open questions about non-oblivious decision-tree lower bounds and hardness for weakly read-once linear branching programs. It constructs non-malleable affine extractors with improved parameters and uses them for hardness results and to derandomize lossless lifting.

  • Problem

    Non-trivial lower bounds for non-oblivious decision trees remained an open question, while average-case lower bounds for weakly read-once linear branching programs were also sought.

    Source: §1 · pp. 4–5

  • Method

    The paper constructs explicit non-malleable affine extractors for linear entropy and uses them to derive hardness results and derandomize lossless lifting.

    Source: §1 · p. 5, §1.1.1 · p. 6

  • Results

    The extractors have exponentially small error and support strong average-case hardness for weakly read-once linear branching programs, as well as non-trivial lower bounds for non-oblivious decision trees.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The extractors provide a derandomization of the lossless lifting used for bounded-depth resolution-over-parities lower bounds.

    Source: §1 · p. 5

    The results do not settle the near-maximal non-oblivious local-depth and size targets or the near-maximal non-oblivious degree-2 depth target.

    Source: §1.1.3 · p. 10, §1.1.4 · p. 11

Abstract

from arXiv · show

We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine tamperings without fixed points. For every fixed $0<\eta<1$ and $t$, we also obtain entropy threshold $C_{\eta,t}n/\log n$, output length $\lfloor n^{1-\eta}\rfloor$, and error $2^{-n^{1-\eta}}$ against $t$ tamperings. Our extractors, as well as the directional affine extractors of Li and Zhong (CCC 2024), yield explicit Boolean functions with correlation $2^{-\Omega(n)}$ against weakly read-once linear branching programs of size $2^{\Omega(n)}$. For non-oblivious decision trees, we prove linear depth lower bounds for queries of each fixed degree $r\ge2$. Applying Li's sumset extractor (FOCS 2023) gives depth $\Omega_\delta((n/\ell)\log\ell)$ for growing locality $\ell\le n^{1-\delta}$, where $0<\delta<1$ is fixed. In the same range, directional affine extractors give correlation $2^{-\Omega(n/\sqrt\ell)}$ against local trees of depth $c(n/\ell)\log\ell/\log\log\ell$, for a sufficiently small constant $c>0$. Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<\xi<1$, this gives explicit polynomial-size unsatisfiable CNFs on $N$ variables whose $\mathrm{Res}(\oplus)$ refutations of resolution depth at most $N$ require size at least $2^{(1-\xi)N}$. Separately, parity substitutions give polynomial-size CNFs on $N$ variables with polynomial-size ordinary-resolution proofs for which every $\mathrm{Res}(\oplus)$ refutation of size $S$ and depth $d$ satisfies $d\log(2S)=\Omega(N^2)$. This removes the $\log^2 N$ loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).

1 Introduction

The section presents explicit non-malleable affine extractors and their applications to lower bounds for branching programs and decision trees, as well as proof-complexity tradeoffs. It also outlines decision-tree depth bounds, extractor-based lifting, parity substitutions, and the scope of the branching-program results.

1 Introduction

  • Non-oblivious lower bounds for local and low-degree decision trees were open despite near-maximal bounds in the oblivious setting.The introduction motivates these models through their implications for circuit lower bounds.Source: §1 · p. 5

1.1.1 Non-Malleable Affine Extractors

  • For every fixed integer h ≥ 1 and entropy rate 0 < ρ ≤ 1, an explicit extractor is h-non-malleable with output length Ωρ,h(n) and error 2^-Ωρ,h(n).For every affine source X with entropy at least ρn and affine maps T1, …, Th satisfying Tj(x) ≠ x for every x in Supp(X), F(X) is nearly uniform and independent of all tampered outputs together.Source: §1.1.1 · pp. 6–7

1.1.2 Lower Bounds for Linear Branching Programs

  • Non-malleability under nonzero translations yields average-case hardness for weakly read-once linear branching programs, and affine non-malleability improves the entropy-gap term in the hardness bound.The paper also gives an explicit Boolean-function family with exponential average-case hardness for programs of exponential size.Source: §1.1.2 · pp. 7–8

1.1.3 Low-Degree Decision Trees

  • For non-oblivious degree-2 decision trees, directional affine extractors with error 2^-E imply depth at least E−1 when k ≤ ⌈n/2⌉−1.The paper also gives exact depth bounds and extractor-based constructions with specified output, error, and entropy parameters; these do not resolve the general open question of nearly maximal non-oblivious depth.Source: §1.1.3 · pp. 9–10
  • For every fixed query degree r ≥ 2, the constructions yield linear non-oblivious decision-tree depth at a sufficiently small fixed entropy rate.For degree r, the stated depth is E/2^(r−2)−O_r(1) under the passage’s multi-tampering, entropy, and error conditions; oblivious trees have twice this lower bound.Source: §1.1.3 · p. 10
  • For fixed r ≥ 2, every nonzero output parity has decision-tree depth Θρ,h,r(E) in the stated fixed-entropy-rate construction.The construction allows m + E ≤ cρ,h n; at m ≤ E, error n^-Θ(1) gives depth Θ(log n), while error 2^-Θ(n) gives depth Θ(n).Source: Then every nonzero output parity f… · pp. 10–11, §1.1.3 · p. 10

1.1.4 Non-Oblivious Local Decision Trees

  • For ℓ ≤ n^(1−δ), an explicit sumset-extractor family gives non-oblivious ℓ-local trees a depth lower bound cδ(n/ℓ) log ℓ.Directional affine extractors also yield exponentially small correlation for every nonzero output parity; the results apply to constructions of Li [Li23] and Li and Zhong [LZ24a], as well as this paper’s extractors.Source: §1.1.4 · p. 11

1.1.5 Deterministic Lossless Lifting

  • For every fixed 0 < ξ < 1, explicit polynomial-size unsatisfiable CNFs on N variables require Res(⊕) size at least 2^((1−ξ)N) at resolution depth at most N.The construction deterministically replaces the random gadgets in Efremenko and Itsykson’s lossless lifting.Source: §1.1.5 · p. 12

1.1.6 Overlapping Gadgets and Resolution over Parities

  • Overlapping gadgets give Res(⊕) size 2^Ωa(N) at depth at most aN, including for top-regular and bottom-regular refutations.The construction’s gadgets share input variables; the overlap argument does not require their intersection graph to be an expander.Source: §1.1.6 · p. 12, S satisfies · p. 13

1.1.7 A Quadratic Tradeoff with Short Ordinary-Resolution Proofs

  • d log(2S) = Ω(N^2) for Res(⊕) refutations of the constructed CNFs, which have polynomial-size ordinary-resolution proofs.Parity substitutions remove the log^2 N loss in the short-ordinary-proof tradeoff of Itsykson, Podolskii, and Shekhovtsov [IPS26, Theorem 6.4].Source: S satisfies · p. 13, §1.1.7 · p. 13

1.2 Related Work

  • The reductions address weakly read-once branching programs by requiring each query to lie outside its past query space, but current parameters do not yield size 2^(n−o(n)).The exponential average-case hardness reductions use published extractors [GPT22] [Li23] [LZ24a]; the near-maximal bounds discussed here concern strongly read-once programs.Source: §1.2 · pp. 15–16

1.3.1 Non-Malleable Affine Extractors

  • Shorter initial seeds enable the extractor construction’s single-tampering result at κ = Θη(1/log n).Replacing one linear extraction with successive output doublings reduces the total seed bits fixed to O(si + log n) per iteration.Source: §1.3.1 · pp. 17–18
  • For multiple affine tamperings, successive fixings and affine partitions separate unequal tampered inputs and group coincident ones without requiring entropy in the tampered inputs.The construction retains additional rounds of the affine correlation breaker [CL22, Section 6]. When both sources have sufficient entropy and both output parities are nonzero, the joint guarantee permits interchanging inputs; separate ordinary-affine guarantees handle zero tampered-output parity or a low-entropy tampered image.Source: §1.3.1 · p. 18

1.3.2 Weakly Read-Once Linear Branching Programs

  • The cubic trace function improves the derivative estimate, balancing it with collision probability to obtain exponent 2n/15.The improvement uses the radical of the derivative’s polar form and averages over displacements.Source: §1.3.2 · p. 19

1.3.3 Decision Trees

  • For local trees, logarithmic-entropy sumset extractors yield depth Ωδ((n/ℓ) log ℓ), while directional affine extractors give correlation bounds through a biased coloring and a second-moment argument.The directional-extractor analysis bounds squared correlation by 2^d(2^-t + 2ε) when each leaf has |I| ≥ t; non-malleable affine extractors inherit the needed directional guarantee for every nonzero output parity.Source: §1.3.3 · p. 20

1.3.4 Proof Complexity

  • The lifting argument preserves a strategy for the base formula while answering parity queries, yielding the size–depth tradeoff of Theorem 1.11.The transfer without the additive conditioning term uses a constant-size multiple-tampering extractor and preserves the tradeoff of [IPS26, Theorem 6.1], but does not improve the lifting theorem.Source: §1.3.4 · p. 21
  • The condensation construction gives a quadratic tradeoff for resolution over parities by combining controlled parity substitutions with the lifting theorem of Itsykson, Podolskii, and Shekhovtsov [IPS26, Theorem 6.1].Successive CNF encodings control clause support while compressing the base formula to linearly many variables and logarithmic clause support.Source: §1.3.4 · p. 21

1.4 Organization of the Paper

  • The paper proceeds from extractor tools and constructions to branching-program and decision-tree lower bounds, then to lossless lifting, overlapping gadgets, and the resolution-over-parities tradeoff.Appendices provide auxiliary-input and list-prediction extensions, higher-moment bounds, and detailed calculations for explicit instantiations.Source: §1.4 · pp. 21–22

2 Preliminaries

This section sets up notation and definitions, records affine-conditioning facts and extractor ingredients, and introduces tools used in later constructions and arguments. It covers coding and sampling resources, affine assignment families, safety and gadget conditions, and a query-DAG view of parity-resolution refutations.

2 Preliminaries

  • The conventions identify binary vectors with F2^n, use base-two logarithms, and define polynomial phases and Boolean algebraic degree; affine substitution does not increase degree.Source: §2 · p. 22

2.1 Statistical Distance, Entropy, and Conditioning

  • Statistical distance contracts under deterministic maps, joint error averages over conditioning values, and min-entropy governs the source and conditional-source bounds.A strong extractor also retains its guarantee with average conditional error at most ϵ + 2^-q when average conditional min-entropy is at least k + q and the seed is independently uniform.Source: §2.1 · pp. 22–23

2.2 Affine Sources, Fibers, and Sections

  • An affine source is uniform on a coset, its entropy is the coset dimension, and affine sections select one point from each nonempty fiber.Conditioning on an affine map produces uniform distributions on affine fibers.Source: §2.2 · p. 24
  • Sequentially fixing at most L affine functions leaves an affine source and reduces the entropy of any fixed affine image by at most L.For every possible sequence of values, the conditional support has codimension at most L in the original support.Source: §2.2 · p. 25
  • For a fixed subspace of dimension at least k, all but at most a 2ϵ fraction of seeds give full-rank linear outputs on every translate.This is the common bad-seed guarantee for a strong linear seeded extractor.Source: §2.2 · p. 25

2.3 t-Non-Malleable Affine Extractors

  • The t-non-malleable affine-extractor definition is equivalent to requiring uniform output independent of comparison outputs for jointly affine tuples with no coordinate equal to the source.The equivalent formulation uses the same entropy, output length, and error parameters.Source: §2.3 · p. 26

2.4 Ingredients from Previous Work on Extractors

  • The cited linear seeded extractors [CGL21] have entropy requirement at most CL(r + q), seed length at most CL(r + q + log N), and a tunable seed-length bound.The tunable bound is C(m/t + log N + p + log2(t)(log m + p)).Source: §2.4 · p. 27
  • Prior ingredients include Li’s explicit correlation breaker with advice and bounded-degree affine extractors with linear output and exponentially small error.The bounded-degree extractor has output length floor(γαN), error at most 2^-ξαN, and output-bit degree at most Dα for fixed α > 0.Source: §2.4 · p. 27
  • Explicit constant-distance binary linear codes and Vadhan’s averaging sampler, as stated in [LZ24b, Theorem 2.7], provide uniformly polynomial-time computable ingredients.The sampler uses O(q + log N) uniform bits to sample O(q) positions and misses all ones with probability at most 2^-q for any fixed string containing a constant fraction of ones; the directional affine extractor result is used at rate α = 1/2 in the advice generator [LZ24a, Theorem 43 and Lemma 53].Source: §2.4 · p. 28

2.5 Proof Complexity Preliminaries

  • Res(⊕) refutations use linear clauses and count line occurrences for size, while resolution depth counts resolution inferences on a longest backward path [IS20, Section 2.2].Odd-charge Tseitin formulas are unsatisfiable because summing their equations gives 0 = 1; on constant-degree graphs their CNF encoding has constant clause width.Source: §2.5 · p. 28
  • A capacity-w family of legal partial assignments avoids falsifying clauses and extends each assignment of size below w on at least one value of any unassigned variable.The families used in the arguments are affine on each fixed domain; restriction closure permits forgetting assigned values.Source: §2.5 · p. 29
  • Safety is equivalent to projected solution-space entropy of at least (ℓ−k)|I| bits on every block set I.Closures select blocks for explicit handling, while simultaneous gadget surjectivity realizes every prescribed output tuple on a nonempty safe affine solution space; individual gadget surjectivity alone does not suffice [EI26, Sections 5–6].Source: §2.5 · p. 29
  • Reversing a Res(⊕) refutation yields a query DAG whose size and resolution depth are preserved, with label rank bounded by clause width.At a resolution node the DAG queries the resolved linear form and follows the falsified premise; weakening steps follow their sole predecessor.Source: §2.5 · p. 30

3 Non-Malleable Affine Extractors

Section 3 develops explicit non-malleable affine extractors by combining affine correlation-breaker, seed-generation, iteration, and blockwise methods, and extends the constructions to multiple affine tamperings and jointly affine inputs. It establishes extraction and independence properties and gives quantitative output-length and error guarantees, including for fixed numbers of tamperings at entropy proportional to n/log n.

3.1 An Affine Correlation Breaker

  • The affine correlation breaker supports both sequentially fixing its output with few affine constraints and obtaining exactly uniform output after intermediate variables are fixed, except on low-probability fixings.These properties are used, respectively, to fix other iterations and to analyze the selected iteration.Source: §3.1 · p. 30

3.1.1 Construction

  • All five construction lengths are O(a + w + q + log n), and the intermediate-variable analysis bounds output distance from uniform after conditioning on a tuple T.The stated constant Ccb = 20 suffices; the analysis also handles a seed with bounded deficiency by comparison to a uniform-seed distribution.Source: §3.1.1 · pp. 31, 32, 34

3.1.2 Exact Uniformity on Affine Fibers

  • On jointly affine inputs, every nonempty fiber of the fixing tuple is affine, and outside the exceptional fibers the breaker output is exactly uniform and affine.The probability of exceptional fibers is bounded using the conditional-distance guarantee.Source: §3.1.2 · p. 34

3.2 Advice Generation and One Iteration

  • The iteration retains Li and Zhong’s initial-seed construction and modifies advice generation and the correlation breaker for jointly affine inputs.Combining iterations uses a bounded-degree initial-seed function and successive fixings of affine functions, with entropy assumptions allowed on either member of a jointly affine pair.Source: §3.2 · pp. 34–35

3.2.1 An Advice Generator for Jointly Affine Sources

  • The explicit advice generator combines codeword sampling with a linear seeded extractor to bound collisions, and uses advice and seed lengths O(p + log n).Its collision probability is at most 2^-p: sampling handles differences with small remaining entropy, while the extractor handles large-entropy differences.Source: §3.2.1 · pp. 35–36

3.2.2 Growing a Uniform Affine Row

  • A short uniform row is grown through successive linear seeded extractions, with intermediate fixings remaining affine.For error 2^-p, each extraction can output up to twice its input length when the input length is at least C0(p + ⌈log n⌉ + 1).Source: §3.2.2 · p. 36
  • Growing an affine row yields an exactly uniform R-bit row after fixing fewer than 2q*R bits, except with total probability 2J·2^-p.The final rows remain affine on each part of the partition, and the final rows themselves are not fixed.Source: §3.2.2 · p. 37

3.2.3 Low-Degree Initial Seeds

  • Low-degree initial seeds use linear somewhere condensers, bilinear inner-product maps, and an affine somewhere-random extractor to produce seed bits.The condensers map local and global affine sources to entropy rate above 1/2; the somewhere-random extractor provides output length and error at least r/(2T)^A0 log(2T), with coordinate degree at most (2T)^A0.Source: §3.2.3 · pp. 37–38

3.2.4 One Iteration

  • One iteration grows an initial seed of O(u + log n) bits into the O(s + log n)-bit row needed by its advice generator and correlation breaker.The iteration combines the initial-seed function, row growth, advice generation, and an affine correlation breaker; its definition applies to every prescribed seed, not only the input’s generated seed.Source: §3.2.4 · p. 39

3.2.5 Properties of One Iteration

  • For jointly affine, pointwise-distinct inputs, one-iteration output is exactly uniform affine on one input and fixed on the other, except on a low-probability partition.The iteration also fixes its output using O(s + log n) affine constraints for a fixed seed; with the local block fixed, at most As,u + O(s + log n) bits suffice.Source: §3.2.5 · p. 40

3.3 Amplification by Majority

  • The majority amplifier replaces disjoint products in Li and Zhong [LZ24a] with majority blocks of length 16D^2 + 1.Its correlation guarantee against bounded-degree polynomial phases uses the result of Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola [CHL+26], and allows D to grow with s.Source: §3.3 · pp. 41–42

3.4 Combining the Outputs

  • Combining iterations applies majority to disjoint bit groups, maps the values through code matrices, and XORs the resulting strings, replacing disjoint products in [LZ24a].The proof selects an iteration with enough conditional entropy, fixes other outputs, and uses the majority correlation theorem while allowing the iteration count and initial-seed degree to grow with n.Source: §3.4 · p. 43

3.4.1 The Construction

  • The combined construction is an ordinary affine extractor and satisfies the non-malleability guarantee for affine maps with no fixed point on the source support.The proof obtains the ordinary extractor guarantee using an artificial shifted pair, then converts Fourier-correlation bounds into statistical non-malleability; the construction is explicit when its components are uniformly computable in polynomial time.Source: §3.4.1 · p. 44, §3.4.4 · p. 47

3.4.2 A Good Block in a Jointly Affine Pair

  • A jointly affine pair has a rank-selected block and side whose entropy survives the joint-prefix conditioning and successive affine restrictions needed by the local condenser.The choices depend only on the original conditional ranks, not on the fixed prefix value.Source: §3.4.2 · pp. 44–45

3.4.3 Bounding Correlations between the Two Outputs

  • Fourier correlations between the two outputs are bounded using the selected block: each later-seed guess contributes at most the exceptional probability plus an exponential error.Summing over guesses of later initial seeds yields the correlation bound; the proof partitions the source into affine cells and applies the local correlation estimate on nonexceptional subcells.Source: §3.4.3 · pp. 45–46

3.4.5 Choosing the Output Lengths

  • The output length can be set to at most one eighth of the minimum chosen error scale, with the non-malleability error controlled by that minimum scale.A geometrically decreasing sequence of error parameters supports the schedule; iteration seed lengths are O(ui + log n), while output lengths and fixed affine functions are O(si + log n).Source: §3.4.5 · p. 47, §3.5.1 · p. 48

3.5.2 Dependence on the Entropy Rate

  • For Eρ = n·2^(-C/ρ) ≥ C log n, the construction gives a uniformly explicit non-malleable affine extractor with entropy threshold ⌈ρn⌉, at least ⌊Eρ⌋ output bits, and error at most 2^(-Eρ).For fixed ρ > 0, this yields linear output and exponentially small error for sufficiently large n.Source: §3.5.2 · pp. 49–50

3.5.3 Entropy of Order n/ log n

  • At entropy rate ρ = Cη/log n, the one-tampering extractor outputs ⌊n^(1−η)⌋ bits with error at most 2^(−n^(1−η)).When ρ^−1 = o(log n), the same estimate gives output length and error exponent n^(1−o(1)), including fixed inverse-polylogarithmic rates (log n)^−τ for 0 < τ < 1.Source: §3.5.3 · p. 50

3.5 Setting the Parameters

  • Uniform parameter choices use dyadic lower approximations to the rate, and the theorem’s size hypothesis bounds component parameters polynomially while source-dependent partitions remain analysis-only.The row-growing schedule has at most ⌈log n⌉ stages; the construction computes majority by counting input bits and requires no polynomial expansion.Source: §3.5.4 · p. 50

3.6 Several Affine Tamperings

  • For several affine tamperings, independence-merging rounds from Chattopadhyay and Liao [CL22, Section 6] keep the original output nearly uniform given the tampered outputs jointly.The section says the entropy requirements are tracked through the iteration and final combination to obtain the quantitative dependence on the number of tamperings.Source: §3.6 · p. 50

3.6.4 Equalities among the Tampered Inputs

  • Partitioning the joint support by equality patterns makes each pair of tampered inputs always equal or always distinct, apart from a small exceptional set.The section records this partitioning approach for handling equalities among tampered inputs.Source: §3.6 · p. 51, §3.6.4 · p. 57

3.6 Several Affine Tamperings

  • Linear output length and exponentially small error are achieved for every fixed number of affine tamperings that have no fixed points on the source support.The maps need not be invertible, and distinct maps may have coincident outputs.Source: §3.6 · p. 51

3.6.1 The Additional Correlation-Breaker Rounds

  • Additional correlation-breaker rounds condition on several comparison outputs while preserving an affine honest output that is exactly uniform except on fixings of small total probability.With fixed seed and advice, the output is determined by successively fixing only O_h(a + w + q + log n) affine functions of the input.Source: §3.6.1 · pp. 52–53

3.6.2 Quantitative Correlation-Breaker Costs

  • For some absolute integer C0, evaluation cost and all entropy requirements for the selected source are at most C q*^C0 (s + log n).The recurrence gives Eν ≤ 256 q*^3 2^-p after padding to fewer than 2q* comparisons; iteration error is at most 2^-u when u ≥ C log n and bilinear error is at most 2^-8s.Source: §3.6.2 · p. 54

3.6.3 The Quantitative Theorem

  • The theorem’s guarantee applies to jointly affine tuples even when comparison inputs coincide, with no entropy assumption on those inputs.The quantitative theorem gives a uniform output independent of all comparison outputs.Source: §3.6.3 · pp. 54–55
  • m ≥ floor(E*) and error 2^-E* for a uniformly polynomial-time extractor on jointly affine tuples when H∞(X0) ≥ ρn and E* ≥ C log n.The theorem sets E* = n2^-CΨ; its uniform output is independent of the comparison outputs, which need no entropy bound and may coincide.Source: §3.6.3 · p. 55

3.6.4 Equalities among the Tampered Inputs

  • A partition fixing at most P L affine functions leaves exceptional mass P·2^−L and reduces honest-source entropy by at most P L, while making every tampered-input pair equal or distinct on each part.On nonexceptional parts, retaining one representative per equality class preserves pairwise distinctness and prevents a representative from equaling the honest input.Source: §3.6.4 · p. 57
  • Entropy Cη,h n/log n suffices for an explicit extractor against fixed h tamperings, with ⌊n^(1−η)⌋ output bits and error at most 2^−n^(1−η).The same parameters give the jointly affine tuple guarantee.Source: §3.6.4 · p. 57
  • For fixed h and 0 < ρ ≤ 1, prescribed m-bit output and error at most 2^−E are available for jointly affine tuples when E ≥ log n and Gρ,h(m + E) ≤ n.The degree bounds and number of affine bits fixed retain the parameter dependence of the underlying proof.Source: §3.6.4 · p. 57

4 Linear Branching Programs

This section develops correlation-based hardness bounds for weakly read-once linear branching programs from directional and non-malleable affine extractors, using decorrelation across affine sections. It extends these bounds to independent uniform auxiliary inputs and sharpens affine non-malleability and no-auxiliary-input bounds.

4.1 The Model and the Decorrelation Condition

  • Directional derivative bias β yields (q, β) section decorrelation when 2q − n ≥ K, while non-malleability against globally fixed-point-free affine involutions yields (k, 2ε) decorrelation.These are the two routes to the shared section-decorrelation condition used in the branching-program reduction.Source: §4.1 · p. 59

4.2 Normalizing the Program and Choosing a Cut

  • A normalized full program has a cut of at most 2s nodes, and future transcripts at each cut node define disjoint affine sections that partition inputs and encode suffix outputs.The normalization has O(ns) vertices; the cut supports the correlation argument by separating past answers from future transcripts.Source: §4.2 · pp. 60–61

4.3 The Correlation Bound

  • Section decorrelation bounds correlation with size-s weakly read-once programs, and non-malleability improves the collision term only when extractor error does not dominate it.The directional-extractor reduction uses a cut of rank ⌈(n + K)/2⌉, while the non-malleable reduction uses rank k.Source: §4.3 · pp. 61–63
  • For fixed r, a (2r − 1)-non-malleable affine extractor yields a moment-based size lower bound for constant prediction advantage, with the entropy-gap term multiplied by r and the error exponent unchanged.The moment argument controls tuples with a section of odd multiplicity; the remaining all-even tuples have probability at most (2r − 1)!! 2^-r(n-k).Source: §4.3 · p. 63
  • The cubic trace function gives stronger weakly read-once hardness through averaging restricted-derivative ranks, and its bounds extend to auxiliary uniform bits and all sufficiently large input lengths.The construction applies the same cubic formula to the first 3⌊N/3⌋ bits at sufficiently large length N.Source: §4.3 · pp. 63–64
  • For weakly read-once linear branching programs, published directional affine extractors [GPT22] [LZ24a] or Li’s non-malleable affine extractor [Li23] yield the qualitative exponential lower bound; the paper’s construction gives further instances at every fixed positive entropy rate.Source: §4 · p. 58, §4.3 · p. 64
  • Independent uniform auxiliary inputs preserve the directional bound; affine non-malleability has collision term 2^-(n-K-1) at a cost of one entropy bit.Source: §4.3 · p. 64
  • For full-output and list prediction, Theorems A.5 and A.6 assume k ≤ n-2, ε ≤ 1/2, sink lists of at most J values, and p = J/2^m ≤ 1/2.Source: §4.3 · p. 64
  • Without auxiliary inputs, the exponent improves from n-k-1 to n-k, and a higher-moment version appears in Theorem A.8.Source: §4.3 · p. 64

5 Decision Trees

This section develops decision-tree depth lower bounds from affine and sumset extractors or dispersers, covering non-oblivious trees with low-degree or local queries and oblivious local trees. It also analyzes correlation and depth transfers, extractor evaluation, and parameter constraints in these reductions.

5.1.1 Degree-2 Queries and Correlation

  • For nonzero output parities, quadratic correlation is at most 2ε + (1 − 2ε)2^-n under directional affine extraction, or 2ε for ordinary extraction at k ≤ ⌈n/2⌉−1.The resulting uniform-input error-δ depth bounds are log2((1 − 2δ)/Γn) and log2((1 − 2δ)/(2ε)), respectively.Source: §5.1.1 · pp. 64–65

5.1.2 Exact Depth Bounds

  • For exact computation, a degree-2 tree needs depth d with 2^d − 1 ≥ n − k + 1, and computing the full vector requires depth at least m.The structural bounds also use affine spaces in common zero sets of quadratic polynomials; such a space can pass through any specified common zero.Source: §5.1.2 · p. 66

5.1.3 Feasible Error Parameters

  • For a Boolean affine extractor at dimension k, log2(1/ε) ≤ k/2 + 1; when k = o(n), the sharper bound is log2(1/ε) ≤ (k + 1)/2 + o(1).Thus the error-dependent exact-depth term alone cannot yield depth n − o(n) at sublinear entropy; the construction’s error 2^-n^(1−η) is consistent because n^(1−η) = o(k).Source: §5.1.3 · p. 67

5.1.4 Computing the Construction by Non-Oblivious Queries

  • With uB ≥ log n, the extractor construction can be computed exactly by a non-oblivious degree-2 tree, using degree-2 queries for bilinear seed-matrix bits and affine queries thereafter.The same depth bound applies after any fixed postprocessing.Source: §5.1.4 · p. 68

5.1.5 Choosing the Output and Error Parameters

  • For fixed κ and m + E ≤ cκn, the evaluation depth is Oκ(m + E + log n); with κ = Θ(log log n / log n) and m = E = ⌈n^(1−η)⌉, it is at most n^(1−η) + o(1).These choices hold for fixed 0 < η < 1 and preserve uniform polynomial-time computability.Source: §5.1.5 · p. 69

5.1.6 Computing the Construction for Several Tamperings

  • For fixed 0 < ρ ≤ 1 and h, when m + E ≤ cρ,h n, the construction for h tamperings has error at most 2^-E and degree-2 evaluation depth Oρ,h(m + E + log n).For fixed h, one may take Cρ,h = 2^O_h(1/ρ); the same upper bound holds for every query degree r ≥ 2.Source: §5.1.6 · pp. 70–71

5.1.7 Comparison at Matched Parameters

  • At fixed entropy rate, degree-2 non-oblivious depth is Θρ(n), matching the construction’s upper bound up to constants; the construction also separates non-oblivious from oblivious queries.The comparison concerns every nonzero output parity; the same function’s oblivious depth is n−o(n).Source: §5.1.7 · pp. 71–72

5.2.1 Correlation and Decision Trees

  • Correlation bounds for degree-r trees yield depth and leaf lower bounds; with uniform-input error η<1/2, the depth bounds shift by log2(1−2η), and zero-error randomized computation requires expected queries at least log2(1/δ).Here δ bounds the maximum correlation with degree-r polynomials, and the expected-query bound applies to randomized non-oblivious trees.Source: §5.2.1 · p. 73

5.2.2 Non-Malleability under Several Translations

  • Against 2^(2r−2)−1 translations, non-malleability transfers to low-degree correlation and gives fixed-degree depth bounds; at fixed entropy rate, the degree-r depth is Θρ,h,r(E).For fixed r and η, an explicit extractor with threshold ⌈Cη,r n/log n⌉, output ⌊n^(1−η)⌋, and error at most 2^(−n^(1−η)) gives bounds for every nonzero output parity.Source: §5.2.2 · pp. 74–75

5.2 Decision Trees of Higher Degree

  • For fixed degree r≥2 and entropy rate ρ<1/2, non-malleable affine extractors yield linear-depth lower bounds and exponentially many leaves, including for constant-error computation.The section develops two routes to higher-degree bounds: transferring low-degree correlation and finding affine spaces of common zeros.Source: §5.2 · p. 72, §5.2.2 · p. 75

5.2.2 Non-Malleability under Several Translations

  • For a quantified growing range of query degrees, extractors with threshold ⌈ρn⌉, output ⌊n^(1−η)⌋, and error at most 2^(−n^(1−η)) give depth bounds for every nonzero output parity.The section also specializes the translation argument to directional affine non-malleability for degree three.Source: §5.2.2 · pp. 75–76

5.2.3 Common Constant Spaces

  • Affine dispersion gives exact depth lower bounds by bounding the dimension of affine spaces contained in a tree leaf; directional dispersion also yields an oblivious-query bound.The common-zero argument extends the affine-space method to systems of low-degree query polynomials.Source: §5.2.3 · p. 77

5.3 Non-Oblivious Local Decision Trees

  • For non-oblivious local trees, preserving a product of sets along a path gives exact lower bounds, while sumset and directional affine extractors strengthen bounds as locality grows.Queries may depend on previous answers and have arbitrarily overlapping supports; the sumset route gains a log ℓ factor over n/ℓ, and the directional route gives a log ℓ/log log ℓ factor with a correlation bound.Source: §5.3 · pp. 77–78

5.3.1 Preserving a Rectangle Along a Path

  • The rectangle-depth theorem bounds every exact non-oblivious ℓ-local tree computing a function nonconstant on sufficiently large products A×B across a balanced coordinate partition.The argument applies when ℓ≥3 and both coordinate blocks have size at least ⌊n/2⌋.Source: §5.3.1 · p. 78
  • At locality three, the rectangle argument gives d > h−k for sumset dispersers at entropy (k, k); affine dispersers also yield depth bounds above (n−k) at locality two and (n−k)/2 at localities three and four.The affine bounds follow because a leaf preserves an affine space of dimension at least n−d for locality two, or n−2d for localities three and four, and that dimension must be below k.Source: §5.3.1 · pp. 78–79

5.3.2 One Explicit Family for All Localities

  • One explicit Boolean family independent of ℓ has LDT2 depth at least n−O(log n) and LDT3 and LDT4 depth at least n/2−O(log n).The family has uniform bounds for 3 ≤ ℓ ≤ n; it comes from Li’s sumset extractor [Li23].Source: §5.3.2 · pp. 79–80

5.3.3 Logarithmic Overhead from Sumset Extractors

  • For fixed 0 < δ < 1, sumset extractors give depth Ωδ((n/ℓ) log ℓ) against non-oblivious ℓ-local trees when ℓ ≤ n^(1−δ).The bound uses a partition separated across each whole root-to-leaf path; constant extractor error suffices for any fixed prediction advantage, and the result excludes exact computation.Source: §5.3.3 · p. 82

5.3.4 Directional Affine Extractors with Small Error

  • Directional affine extractors give correlation 2^-Ω(n/√ℓ) against non-oblivious ℓ-local trees of depth c(n/ℓ) log ℓ/log log ℓ, for sufficiently small c > 0.The result applies as ℓ grows and ℓ ≤ n/(Cρ log n); it also follows for nonzero output parities of the paper’s non-malleable affine extractors, and applies to Li and Zhong’s published directional affine extractors [LZ24a].Source: §5.3.4 · p. 84

5.3.5 Parameters for Oblivious Local Trees

  • For oblivious ℓ-local trees, a polynomial-time computable function from [GG26] requires depth at least n−2m+1 when ℓ log^(C−1) n = o(n).The parameters C′ > C > 1 and the output length m are supplied by the sumset-condenser and concentration-theorem construction.Source: §5.3.5 · pp. 84–85
  • Theorem 5.2 of [GG26] yields depth at least d + 1; the parameter analysis reaches depth n − o(n) with overhead ℓd/n = Ω(n/(log^(C−1)n log log n)).These are consequences of [GG26]’s technical theorems, not a new condenser or a resolution of the linear-overhead question.Source: §5.3.5 · p. 85
  • In this reduction, linear locality and linear depth force linear output length; the small-output formulation matters because the identity map already has depth n by output count.This limitation concerns the reduction, not an inherent limitation of the tree lower bound.Source: §5.3.5 · p. 86
  • A selector conversion loses a factor m: depth lower bound D for F gives only t ≥ D/m for the selected-bit function, on n + ⌈log m⌉ input bits.For F(x) = x and ℓ > ⌈log m⌉, the selected-bit function has an oblivious tree of depth at most ⌈n/(ℓ−⌈log m⌉)⌉, despite vector depth n.Source: §5.3.5 · p. 86
  • Li’s logarithmic-entropy sumset extractor [Li23, Theorem 7.13] has one output bit and constant error, so it cannot directly replace the longer-output strong extractor used for the seed.Improving this route would require a longer strong output at that entropy or a different reduction avoiding Eqn. (5.45).Source: §5.3.5 · p. 86

6 Lower Bounds for Resolution over Parities

This section develops lower bounds for resolution over parities, using extractor-based lifting and restrictions, parity substitutions, and constructive compression tools. These methods yield CNFs with exponential size requirements at linear depth and quadratic depth–size tradeoffs, including formulas with polynomial-size ordinary-resolution proofs.

6.1 Deterministic Lossless Lifting

  • For every fixed 0 < ξ < 1, explicit unsatisfiable CNFs with polynomially many clauses of width Oξ(log N) require Res(⊕) refutations of size at least 2^((1−ξ)N) at depth at most N.The construction is deterministic polynomial time and counts the actual variables; the bound does not cover unrestricted-depth refutations.Source: §6.1 · p. 86, §6.1.2 · p. 88

6.1.1 A Deterministic Family of Lossless Gadgets

  • For rank-spread affine sources, one deterministic family of gadgets is simultaneously surjective on every source, using block length ℓ = C⌈log r⌉ + C0 and polynomial construction time and truth-table size.The construction combines a universal rank certificate with a fixed-tampering non-malleable affine extractor; Fourier decay lets it sum all nontrivial coefficients below one.Source: §6.1.1 · p. 87, §6.1 · p. 87

6.2.1 The Substitution

  • The substitution shares each raw input block between exactly two gadgets, replaces each base variable by a function of incident blocks, and yields an unsatisfiable ordinary CNF constructible in polynomial time.For constant graph degree and base width, with t = O(log m), it needs neither extension variables nor a preimage-sampling algorithm.Source: §6.2 · p. 89, §6.2.1 · p. 89

6.2.2 Product Bounds from Directional Affine Extractors

  • Directional affine extractors control gadget correlations while several input blocks remain free; non-malleable affine extractors also provide estimates with one free block under unrelated invertible affine coordinate changes.For distinct free-block values, the directional-extractor argument bounds the relevant conditional correlation by 2ε.Source: §6.2 · p. 89, §6.2.2 · p. 90

6.2.5 The Size–Depth Tradeoff

  • For fixed-degree sharing graphs, non-malleability yields a restriction to disjoint three-bit majority gadgets, removing an additive conditioning term and giving coefficient 2^-O(D) in the quadratic size–depth bound.Blocks of length at most 2CD suffice, and the lifting theorem of [IPS26, Theorem 6.1] applies.Source: §6.2 · p. 89

6.2.3 Affine Restrictions and a Monotone Closure

  • On κ-safe affine spaces where each active gadget retains at least d0 free blocks, every pattern on b active outputs has probability between (1 − θ)2^-b and (1 + θ)2^-b.A row-space-dependent monotone closure leaves the projected row space safe while identifying closed gadgets, enabling equations to be forgotten and proof paths restarted.Source: §6.2.3 · pp. 90–91

6.2.4 Extension, Forgetting, and the Rank Bound

  • Under the affine-state invariant, every refutation of the substituted formula contains a clause of rank at least L.The invariant lets an adversary answer parity queries and forget equations while maintaining a nonempty affine set on which no initial substituted clause is identically false.Source: §6.2.4 · pp. 92–93

6.2.5 The Size–Depth Tradeoff

  • For a legal family of capacity w, every refutation has depth at least L, and the auxiliary parameter p is at most ν + ⌈log S⌉; affine families may take ν = w.The bounds permit arbitrary separate invertible affine maps.Source: §6.2.5 · p. 93

6.2.6 An Explicit Family of Formulas

  • Refutations of explicit polynomial-size, width-O(log N) unsatisfiable CNFs require size 2^Ω_a(N) at depth at most aN, for every fixed a > 0.The formulas are built from odd-charge Tseitin systems on explicit constant-degree expanders.Source: §6.2.6 · p. 96
  • The expander result is an overlapping-gadget transfer, not an improvement over the strongest disjoint-substitution size–depth bounds; its additive O(N/log N) term remains significant beyond linear depth.The asymptotic statement concerns the sizes supplied by the expander family.Source: §6.2.6 · p. 97

6.2.7 Tagged Affine Non-Malleability and One Free Block

  • The tagged matching bound controls character moments using the size of a maximum matching, and the expectation vanishes when the character is nonzero on an unrelated free block.Affine non-malleability leaves at most one free block per active gadget and removes peeling from the closure, including under unrelated affine maps.Source: §6.2.7 · pp. 97, 99
  • Tagged lifting gives refutation bounds through rank Ltag = ⌊κDw/2⌋, with ν = w or the affine-family value from Eqn. (6.16).The result applies for coupling graphs of any fixed degree D ≥ 1.Source: §6.2.7 · p. 98

6.2.8 Transfer through Majority Restrictions without the Conditioning Term

  • For each fixed D, polynomial-time constructible overlapping gadgets preserve the size–depth tradeoff of [IPS26, Theorem 6.1] under unrelated local affine coordinate changes, yielding d log(2S) ≥ 2^-O(D)N^2.Source: §6.2.8 · p. 102

6.3 A Quadratic Size–Depth Tradeoff with Short Resolution Proofs

  • d log(2S) = Ω(N^2) for explicit unsatisfiable N-variable CNFs with polynomial-size ordinary-resolution proofs, improving the tradeoff for this family by removing a log^2 N loss.The construction is separate from the extractor-based lifting; depth d(N) = o(N^2/log N) does not polynomially simulate ordinary resolution on this family.Source: §6.3 · pp. 102–103

6.3.1 Depth-Preserving Partial Condensation

  • If 2(W + 1) ≤ r, partial condensation converts a width-W, depth-d refutation of the encoded F(y, Ax) into one for F(y, z) of width at most W + 1 and depth at most d.The parity substitutions may share variables, while a disjoint set y of original variables may remain unchanged.Source: §6.3.1 · p. 103

6.3.2 Two Constructive Matrix Lemmas

  • A deterministic grouped-matrix construction expands every nonzero input a with wt(a) ≤ B to wt(Ta) ≥ 2 wt(a), while each input group reaches O(q) outputs in total.The construction uses scales with reused routing labels; the passage also describes a second matrix with constant row weight.Source: §6.3.2 · pp. 104–105
  • Lemma 6.25 constructs binary matrices with at most sixteen ones per row and n ≤ CgM/L columns when M ≥ CL6.The construction runs in poly(M) + exp(O(L^(2κ) log L)) time, for absolute constants and κ < 3; deleting rows preserves its stated expansion properties.Source: §6.3.2 · p. 106

6.3.3 Uniform Recursive Support Bounds

  • Lemma 6.26 bounds recursion depth by H(q), final output length by BD(K + 1)H(q), and each original group’s prefix support by CPq.Each active map expands through weight B, and its construction takes poly(B, 2q) time with a fixed exponent.Source: §6.3.3 · p. 108

6.3.4 Compressing and Merging the Terminal Parts

  • Lemma 6.27 gives a uniformly polynomial-time continuation with at most Ab final variables, O(1 + H(q)) stages, and O(q) prefix support per original group.Each active map expands through weight b.Source: §6.3.4 · p. 110

6.3.5 The Base Formula, Clause Encodings, and Variable Count

  • The condensed formula cannot have a refutation of width at most floor(b/4) and depth below b^2.Reversing the substitution stages would give a refutation of the base formula with width below b/2 and the same depth, contradicting its depth lower bound.Source: §6.3.5 · p. 112
  • d log(2S) = Ω(N^2) for every Res(⊕) refutation of the constructed polynomial-size CNFs, which also have polynomial-size ordinary-resolution proofs.The lifting uses disjoint three-bit majority gadgets; the final construction has exactly N variables.Source: §6.3.5 · p. 112

A.1 Independent Uniform Auxiliary Variables

This section extends branching-program hardness reductions to programs with independent uniform auxiliary inputs. The reductions use cuts based on pure-input query rank and retain bounds independent of the number of auxiliary bits.

A.1 Independent Uniform Auxiliary Variables

  • A cut with at most 2s markers is placed where pure-input query rank reaches q, and each marker has affine sections whose projected maps share a rank-q map.The cut-marker prefix space is common to all paths reaching that marker.Source: §A.1 · p. 117
  • The directional-hardness theorem applies to programs on (X, R), where X and R are independent uniform inputs, and its bound has no dependence on t.Its hypothesis is a directional derivative bias bound at entropy K, with q < n and 2q − n ≥ K.Source: §A.1 · p. 118
  • The affine-hardness reduction also handles independent uniform auxiliary inputs, with no dependence on t, assuming non-malleability against globally fixed-point-free affine involutions.The proof uses q = k + 1 and applies the intersecting-projected-sections lemma to pairs of projected sections.Source: §A.1 · p. 119

A.2 Full-Output and List Prediction

The section establishes full-output and list-prediction bounds for weakly read-once linear branching programs, including programs with independent uniform auxiliary inputs. It then notes that higher-order non-malleability improves the collision term in subsequent reductions.

A.2 Full-Output and List Prediction

  • For single full-output prediction, the baseline list probability is p = 2^-m, so the collision contribution includes a factor of 2^-m.For lists, p = J/2^m.Source: §A.2 · pp. 119–120
  • The list-prediction bound extends to programs with independent uniform auxiliary inputs, at a one-bit loss in the collision exponent.The stated bound is independent of the number of auxiliary bits, and globally fixed-point-free affine involutions suffice.Source: §A.2 · pp. 120–121
  • The additional term m − log J concerns full-output or list prediction and does not improve the Boolean-prediction bound.This marks the scope of the list-prediction refinement.Source: §A.2 · p. 122

A.3 Higher Moments for Several Affine Tamperings

  • Higher-order non-malleability improves the collision term by making the original output nearly uniform and jointly independent of the tampered outputs.The tampered maps may coincide with one another.Source: §A.3 · p. 122

A.3.1 Boolean Prediction

Higher moments strengthen the Boolean-prediction size bound by improving its collision-limited exponent. They do not improve the extractor-error exponent, and using order 2r requires non-malleability against at least 2r − 1 tamperings.

A.3.1 Boolean Prediction

  • Non-malleability against globally fixed-point-free affine involutions suffices for the reduction.In the moment expansion, even repetitions of a sign cancel; the all-even tuples contribute the collision term.Source: §A.3.1 · p. 122
  • For fixed r and constant η > 0, with ε = 2^-E, the size bound is s ≥ 2^min{E,r(n − k)} − O_{r,η}(1).The moment order must satisfy 2r − 1 ≤ h.Source: §A.3.1 · pp. 122–123
  • An order-2r moment can raise the collision-limited exponent from n − k to r(n − k), but does not multiply the extractor-error exponent.To reach the error-limited exponent up to an additive constant, it suffices that r ≥ E/(n − k) and h ≥ 2r − 1, with r fixed.Source: §A.3.1 · p. 123

A.3.2 List Prediction

The list-prediction extension analyzes centered list indicators with higher moments, whose repetitions do not cancel like Boolean signs. Its bound includes a second term needed when the baseline list success probability is small.

A.3.2 List Prediction

  • For list prediction, the baseline success probability is p = J/2^m, and the higher-moment theorem applies to sinks carrying lists of at most J distinct outputs.Unlike Boolean signs, centered list indicators do not cancel under even repetitions; their ideal moment is a scaled binomial central moment.Source: §A.3.2 · p. 123
  • When p ≤ 1/2, the higher-moment bound includes a second term needed when Bp is small.The moment expansion has no contribution from a suffix index occurring exactly once because the centered indicator has zero first moment.Source: §A.3.2 · p. 124

A.3.3 Higher Moments with Auxiliary Variables

Higher moments sharpen the collision term in the size bound for weakly read-once branching programs with independent uniform auxiliary variables, while leaving the extractor error exponent unchanged. The analysis controls moment contributions through singleton projected values and applies when queries mix original and auxiliary variables.

A.3.3 Higher Moments with Auxiliary Variables

  • The bound has no dependence on the number of auxiliary variables, and queries may mix original and auxiliary variables arbitrarily.The theorem concerns a size-s weakly read-once linear branching program on independent uniform inputs X and R.Source: §A.3.3 · p. 125
  • The proof bounds the sign-product expectation by applying h-non-malleability to affine sections and fixed-point-free affine involutions.It controls moment tuples by the number of projected values occurring exactly once, then averages bounds over independent uniform projected inputs.Source: §A.3.3 · pp. 125–126
  • The collision estimates use the probability of no singleton among L draws and bound it by D_L B^-r for equality partitions with at most r blocks.Here D_L counts partitions of [L] whose blocks all have size at least two.Source: §A.3.3 · p. 126
  • Higher moments improve the collision term in the size bound for constant prediction advantage, but leave the extractor error exponent unchanged.Using a higher moment requires non-malleability against more tamperings and may worsen the extractor's output and error constants.Source: §A.3.3 · p. 126

A.4 Explicit Instantiations

The explicit instantiations use the cubic trace function and affine extractors to derive lower bounds for weakly read-once branching programs. The cubic-trace analysis averages derivative ranks across displacements between affine sections, including sections that may intersect.

A.4 Explicit Instantiations

  • The cubic-trace argument strengthens the worst-case derivative-bias bound by averaging derivative ranks over possible displacements between affine sections.The sections need not be disjoint.Source: §A.4 · pp. 126–127
  • For m ≥ 3 and d = ⌊2m/5⌋, the correlation bound is at most 5s·2^-d when 15 divides n.The proof uses the cubic trace function and its affine-section estimates.Source: §A.4 · pp. 127–128
  • Exact computation of the extended cubic trace function requires size at least 2^(2N/15−O(1)).The construction extends to arbitrary input lengths by applying the function to three blocks and treating up to two leftover bits as auxiliary inputs.Source: §A.4 · p. 128
  • For s ≤ 2^n/36 and sufficiently large n, the stated bound is at most 2^-n/36, yielding the agreement-advantage assertion.The passage identifies agreement advantage as half the correlation.Source: §A.4 · p. 128
  • The extractor-based instantiations include Li and Zhong's directional affine extractor [LZ24a], Li's non-malleable affine extractor [Li23], and the paper's Theorem 1.2.The auxiliary-input extension applies to these affine instantiations as well.Source: §A.4 · p. 129

B Proof of Deterministic Lossless Lifting

This section proves the rank-certificate theorem underlying the gadget construction, then develops the sparse inconsistent system and the arguments needed for the lifting theorem.

B Proof of Deterministic Lossless Lifting

B.1 Rank Certificates and the Fourier Bound

The section defines rank certificates to organize affine input blocks into clusters and outside classes, then uses non-malleability to bound cluster products. Three linear-algebra lemmas supply rank-capacity, projection-rounding, and block-completion tools.

B.1 Rank Certificates and the Fourier Bound

  • A cluster-product bound applies when jointly affine input blocks have a rank certificate and the extractor meets the stated entropy and tampering conditions.The certificate parameters are (M, H, q, k, k′), and the comparison maps may be singular or coincide.Source: §B.1 · pp. 129–130
  • Each cluster's honest block supplies an entropy-k source, while non-malleability bounds the phase mean on good clusters and bad clusters are handled by their probability.The tagged inputs form a jointly affine tuple; the proof bounds bad-event probabilities using joint rank.Source: §B.1 · pp. 130–131

B.2 Three Linear-Algebra Lemmas

  • The rank-capacity lemma expresses the maximum feasible total allocation through a minimum over partitions into T*, T0, and T1.Its objective combines a weight for T* with conditional ranks relative to two conditioning spaces.Source: §B.2 · p. 131
  • Boolean projection rounding produces a coordinate labeling map whose error is bounded by 72d.The proof first approximates the coordinate functions by linear forms, then replaces coordinates that fail multiplication by zero.Source: §B.2 · pp. 131–132
  • A block-diagonal matrix D can be chosen so rank(M − D) ≤ 5t, where t is the maximum rank across a block cut.Source: §B.2 · p. 132

B.3 Certificates for Every Rank-Spread Source

This appendix constructs a universal rank certificate for rank-spread sources through normalization and repair, followed by alignment and selection of blocks with private rank.

B.3 Certificates for Every Rank-Spread Source

  • The certificate guarantees at least αN honest blocks, cluster size at most H, at most Q outside classes, and thresholds at least βℓ.The stated constants also apply to every nonempty subset of blocks.Source: §B.3 · p. 132

B.3.1 Normalization and Repair

  • Normalization restricts the source and enlarges it while preserving individual block images, yielding q internally independent families and a monotone rank defect bounded by block weights.It also ensures that at least N−N/[χ(η−σ)] blocks have rank at least σℓ in the restricted source.Source: §B.3.1 · p. 133
  • Repair loses at most 4W/k targets and leaves threshold at least k/4 when k ≥ 2 and λ = ⌊k/2⌋.The repaired certificate preserves surviving original clusters and adds at most two outside classes.Source: §B.3.1 · p. 134

B.3.2 Alignment and Selection

  • Alignment approximates the inclusion map by a block-diagonal map with rank error at most 361g.The construction groups columns by original labels and applies the block-diagonal approximation theorem.Source: §B.3.2 · p. 135
  • Simultaneous selection yields at least m/[4(∆+Bℓ/a)] pairwise disjoint proposed clusters with honest private rank at least k.The selection argument samples clusters and removes intersections and clusters failing the private-rank test.Source: §B.3.2 · p. 135

B.3.3 Assembly of the Independent Families

Assembly combines an existing certificate with fresh internally independent families, using peeling, alignment, and selection to retain clusters with private and joint rank guarantees.

B.3.3 Assembly of the Independent Families

  • The assembled arrangement retains honest blocks among the originals, with cluster size at most H+d* and a common threshold at least min{κ, δℓ/[8(R+1)]}.The threshold bound requires ℓ ≥ 8(R+1)/δ; the certificate also keeps the old outside classes and partitions unassigned fresh blocks into family classes.Source: §B.3.3 · pp. 135, 136, 138
  • Peeling separates each fresh family into low-capacity remainders and high groups, discarding at most a quarter of the indices globally before assembly.High groups have rank greater than δℓ/2 per index against both sides of a recorded cut.Source: §B.3.3 · p. 136
  • The total rank discrepancy between the inclusion maps and their aligned maps is bounded independently of the number q of fresh families.Restricting the maps to the retained indices only decreases that discrepancy.Source: §B.3.3 · pp. 136–137
  • Selection retains disjoint clusters with private rank k by sampling candidates and controlling conflicts and low-rank losses.The selected indices receive distinct labels within each family.Source: §B.3.3 · p. 137
  • After deletions, every subset of selected indices in a low-capacity remainder has joint core rank at least λ per index against that family’s unassigned blocks.These inequalities hold on the original source, although the restrictions used for different families need not coincide.Source: §B.3.3 · pp. 137–138

B.3.4 Proof of the Universal Certificate Theorem

The proof instantiates normalization, selection, assembly, and repair with constants chosen from η to obtain the universal certificate theorem.

B.3.4 Proof of the Universal Certificate Theorem

  • Normalization with σ = η/2 ensures that at least N/2 blocks have rank at least ηℓ/2.The proof sets χ = ⌈4/η⌉ and ρ = η/(4χ) for normalization and core ranks.Source: §B.3.4 · pp. 138–139
  • Rado’s theorem and selection retain at least ρN/16 honest singleton blocks with private threshold at least ρℓ/4.These singletons become the old arrangement, while the remaining blocks form the fresh families.Source: §B.3.4 · p. 139
  • Assembly gives at least αpN honest blocks, cluster bound 1+d*, and at most q2R+1 outside classes before repair.Both thresholds are at least βpℓ at this stage.Source: §B.3.4 · p. 139
  • Repair with λ = ⌊k/2⌋ loses at most αpN/2 targets and leaves threshold at least βpℓ/4.It preserves the cluster bound, adds at most two classes, and transfers the certificate to the original source.Source: §B.3.4 · p. 139

B.4 Deterministic Formulas and Lossless Lifting

The appendix constructs a sparse inconsistent linear system and uses safe affine systems, closure, and viable query histories to lift it into hard CNFs for Res(⊕).

B.4.1 A Sparse Base

  • The sparse base system has r+1 rows, r columns, row weight at most s, every set of at most β rows independent, and is inconsistent.Its construction is deterministic in time r^{Oδ(1)} for fixed δ.Source: §B.4.1 · pp. 139–140
  • A lossless graph incidence map gives independent columns for sets of at most K columns, while the spectral-graph construction supports the medium-weight bound.The construction combines the lossless-expander incidence map with a polynomial-evaluation map on neighbor tuples.Source: §B.4.1 · pp. 140–141

B.4.2 Legal Assignments and Closure

  • The closure C(F) is the unique inclusion-minimal maximizer of dim(F ∩ V_S) − k|S|; its restricted row space is safe and closure is monotone under adding equations.When closure grows after adding one independent form, the stated dimension relation is given in Lemma B.14.Source: §B.4.2 · p. 142
  • For viable systems of rank below kw, gadget surjectivity on every safe affine system guarantees a viable answer to every parity query.The viability definition bounds closure size by w, with w < γ.Source: §B.4.2 · p. 142

B.4.3 The Boolean Encoding and Counting Argument

  • The Boolean encoding forbids raw tuples whose gadget outputs violate a base row, producing an unsatisfiable CNF with at most (r+1)2^{sℓ} clauses of width at most sℓ.The encoding uses only raw variables.Source: §B.4.3 · p. 142
  • The proof establishes Res(⊕) width at least K0 for Ψ, where K0 = kw, and a successful stopping node has label rank at least K0−b0.A uniform raw assignment agrees with paid answers and reaches the threshold viably with probability at least 2^{-(ℓ−k)w}.Source: §B.4.3 · p. 143
  • The query-count argument uses full history only to count paid queries, while restarts use the actual node label, so rank and query costs remain binary without a log Q factor.The refutation-to-query-DAG conversion preserves size and resolution depth.Source: §B.4.3 · pp. 142–143
Loading 2610.02407v1…