On Top-Down and Local Lower Bounds for $\mathrm{AC^0}$ Circuits

The Chopping Game

• The Chopping Game models top-down reasoning by letting Spoiler retain a dense subset of one input side while Duplicator prunes the other until a coordinate separates them.In each round, Spoiler keeps at least a 1/m fraction of the active side being chopped.Source: §1.1 · p. 2
• Every depth-d, fan-in-m circuit induces a d-round winning Spoiler strategy, so Duplicator survival yields a circuit lower bound.The correspondence is oriented by the output gate, and the Chopping Game is a relaxation of the KW partition step.Source: §1.1 · p. 2, §1 · p. 2

Top-down approximation

• Top-down polynomial approximation gives m = 2^Ω(n^(1/(2(d−1)))) for depth-d AC^0 circuits computing parity.A d-round winning strategy produces a probabilistic F3 polynomial of degree O((log m)^(d−1)), while parity requires approximation degree Ω(√n).Source: §1.2 · p. 3

Local games

• The Distance-k KW Game asks protocols to find a differing coordinate for strings at Hamming distance exactly k, while local Chopping variants impose separation within radius-k neighborhoods.The paper conjectures super-polynomial m in the regime d ≪ k ≪ n.Source: §1.2 · p. 3
• Every d-round affine winning strategy for the k-local parity Chopping Game requires m ≥ n^Ω(k^(1/d)/d), and linear Distance-k protocols also receive growing lower bounds.The proof uses fixed-core sunflower bounds in a round-elimination argument; affine strategies match the form of the best known upper bounds.Source: §1.2 · p. 4

Graph-theoretic conjecture

• The paper formulates a graph-theoretic Distance-k conjecture for finite n-regular graphs of girth greater than 2k as an analogue of PARITY ∉ AC^0.It also defines k-local n-hypercubes and contrasts finite high-girth graphs with the infinite regular tree.Source: §1.2 · p. 4

Circuits

• AC^0 circuits use alternating AND and OR gates, with depth counting internal gates on input–output paths and fan-in bounding gate inputs.Σ_d circuits have OR output gates, Π_d circuits are dual, and literals or constants have depth zero.Source: §2.1 · p. 5

Karchmer–Wigderson Games

• In the KW game, Alice and Bob receive inputs from opposite sides and must output a differing coordinate through an alternating deterministic protocol.An m-ary protocol has at most m possible messages per round, while an L-bit d-round protocol has total cost at most dL.Source: §2.1 · p. 5
• The KW theorem equates Alice-first d-round m-ary protocols with Σ_d formulas of fan-in at most m, with the Bob-first version corresponding to Π_d formulas.The equivalence also extends to circuits by unfolding them into formulas without increasing depth or fan-in.Source: §2.1 · pp. 5–6

Partition Game

• The Partition Game models protocol descent by having Spoiler partition the active side into at most m parts before Duplicator selects one part.The recursive condition requires Spoiler to win from every selected part after the sides reverse.Source: §2.2 · p. 6
• A Partition Game win is equivalent to a bounded-fan-in Σ_d formula separating the two sets.This follows inductively by combining formulas for the parts with an OR gate.Source: §2.2 · p. 6

Chopping Game

• The Chopping Game retains only a dense subset of the active side, lets Duplicator arbitrarily prune the opposite side, and declares victory when a coordinate separates the survivors.Spoiler fixes the chop before seeing Duplicator’s response, and every response defines a possible continuation branch.Source: §2.2 · p. 6
• Every depth-d, fan-in-m circuit induces a d-round winning Chopping strategy, so Duplicator’s survival yields a corresponding circuit lower bound.The implication follows because a largest partition part has density at least 1/m and Chopping permits any subset of that density.Source: §2.2 · p. 7
• Chopping strategies can be strictly more general than circuit descents, so lower bounds for Chopping are stronger than the corresponding circuit lower bounds.For B={0^n} and A={0,1}^n\{0^n}, Spoiler wins a one-round 2-Chopping Game although two-part partitioning requires more than two coordinates.Source: §2.2 · p. 7

Top-down separators

• A winning Spoiler strategy yields both a proper polynomial and a shallow formula that weakly separate A from B.The polynomial proof applies the Razborov–Smolensky construction round by round; the formula proof replaces algebraic OR with ordinary Boolean OR.Source: §3 · p. 7

Polynomial approximation

• Theorem 3.2 constructs a proper F3 polynomial of degree at most (2s)^(d−1), where s = O(log m), from a d-round Chopping strategy.The construction uses one-sided acceptance bounds on the two input sets and proceeds inductively through counterfactual responses to a fixed chop.Source: §3.1 · pp. 7–8
• For arbitrary input sets, the polynomial is a one-sided weak separator: acceptance is small on B but positive, possibly small, on A.The construction sets ρ = 1/(2m) and β = m^-10 and combines recursively obtained polynomials through an algebraic OR over F3.Source: §3.1 · p. 8
• For parity, translation symmetry amplifies the weak separator to constant advantage, producing a polynomial agreeing with parity on more than three quarters of the cube.The resulting degree is at most 4D, and the standard Ω(√n) F3 approximation-degree lower bound gives m = 2^Ω(n^(1/(2(d−1)))).Source: §3.1 · pp. 8–9

Formula approximation

• The formula construction gives a Π_(d−1) AC0 separator with fan-in at most Cm log m and at most (Cm log m)^(d−1) leaves.Its construction uses O(m log m) counterfactual branches, leaving an m^-10 residual on B while maintaining a positive fraction of the chopped side.Source: §3.2 · p. 9
• The formula separator has average sensitivity O((log m)^d), yielding m = Ω(√n/(log n)^(d/2)) for parity.This bound applies to the constructed separator F via its correlation with the top Fourier character, not to arbitrary functions admitting a Chopping strategy.Source: §3.2 · pp. 9–10

Definitions

• The k-local Chopping Game relaxes global separation by requiring a separating coordinate for every point on each surviving side.Exact Distance-k variants restrict relevant pairs to Hamming distance exactly k; a global separator satisfies the k-local condition, which implies the exact-distance condition.Source: §4 · p. 10

Two-round bounds

• (k + 1)⌈log n⌉ is an upper bound on total communication for every fixed k in the two-round Distance-k KW Game.A BCH-code syndrome lets Bob recover x + y and send a differing coordinate; the messages have lengths k⌈log n⌉ and ⌈log n⌉.Source: §4.1 · p. 11
• (k + 1) log n − O_k(1) is a lower bound for every two-round deterministic Distance-k KW protocol.Alice alone must communicate at least k log n − O_k(1) bits, and Bob additionally communicates a differing coordinate.Source: §4.1 · p. 12

Even and odd distances

• k/2 log n − O_k(1) is a round-independent lower bound for even fixed k, implying a message of length at least k/(2d) log n − O_k(1) in d-round protocols.The diagonal argument yields the total-cost bound for arbitrary numbers of rounds.Source: §4.2 · p. 12
• 2⌈log n⌉ is a total-cost upper bound for every odd k.A parity-based binary search maintains a block where the inputs have opposite parity and uses two one-bit messages per stage.Source: §4.2 · pp. 12–13

Conjectures

• The Distance-k and stronger Distance-k Chopping conjectures assert m = n^ω(1) for d ≪ k ≪ n.For fixed d and sufficiently large k, the conjectures require m ≥ n^c for every c; this would qualitatively strengthen PARITY ∉ AC^0.Source: §4.3 · p. 13

Reduction framework

• A linear KW protocol gives an affine Partition Game strategy and, by retaining a largest part, an affine Chopping strategy.The relevant messages are linear maps of the speaker’s input, with L-bit messages represented by matrices having at most L rows.Source: §5 · pp. 13–14
• ELEMXF2(k, n) asks for a coordinate in the support of an unknown weight-k vector using adaptive batches of linear queries over F2.The algorithm receives inner products with query vectors and must output an element of the hidden vector’s support.Source: §5 · p. 14

Scope boundary

• The exact-weight setting remains less understood than the odd-weight ELEMXF2 problem.The cited linear-algebraic search lower bound uses the full odd-weight promise, and the authors do not know how to extend it to exact weight.Source: §5 · p. 14

ELEMXF2 lower bound

• q log n − O_k(q) is a batch-size lower bound for every deterministic q-round ELEMXF2(k, n) algorithm when k^(1/q) is an integer at least 2.The proof repeatedly applies a fixed-core sunflower bound to eliminate query rounds.Source: §5 · pp. 14–15

Affine strategies

• k^(1/d) log n − O_k(1) is the affine Spoiler lower-bound scale, and affine k-local parity strategies require m ≥ n^Ω(k^(1/d)/d).The affine reduction maintains two surviving affine sets related by an unknown translation; one query batch simulates each chop.Source: §5 · pp. 16–17

Graph relation

• The graph Distance-k relation asks each party to output a neighbor leading one step closer to the other endpoint.The parties’ outputs are local directions and need not share a common edge label.Source: §6 · p. 17
• A graph Distance-k Chopping win requires every surviving vertex to have a neighbor satisfying the distance-decrease condition against all relevant opposite-side vertices.The condition is imposed symmetrically on both role-labeled sides.Source: §6 · p. 17

Local hypercubes

• A k-local n-hypercube is a finite connected n-regular graph whose radius-k neighborhoods are rooted-isomorphic to those of the n-dimensional cube.Cayley graphs generated by (2k + 1)-wise linearly independent vectors provide examples.Source: §6.1 · p. 18

Upper bounds

• 2k log n + O(1) bits per message is a two-round upper bound for the graph Distance-k relation on finite n-regular graphs of girth greater than 2k.A coloring separating endpoints of every length-2k path lets each party infer the first edge of the relevant unique geodesic.Source: §6.2 · pp. 18–19

Conjectures

• The high-girth Distance-k conjecture posits graphs where every d-round protocol has maximum message length Ω_d(k log n), with a stronger Chopping formulation requiring m ≥ n^Ω_d(k).The graph degree plays the role of cube dimension, while message alphabet size plays the role of circuit fan-in.Source: §6.2 · p. 19

Finite versus infinite graphs

• log n + O(log k) total cost is achievable on an infinite rooted n-regular tree in three rounds, unlike the finite high-girth setting.The protocol uses the public root, ancestor relations, and port labels; these structures are unavailable in general finite high-girth graphs.Source: §6.3 · pp. 19–20

• The main open problem is proving m = n^ω(1) for the Distance-k KW and Distance-k Chopping Games when d ≪ k ≪ n.Source: §7 · p. 20
• The Chopping Game lower bound currently applies to affine Spoiler strategies, and removing this hypothesis remains an open problem.It would already suffice to prove m ≥ n^γ_d(k) for some γ_d(k) → ∞.Source: §7 · p. 20
• The approximation argument does not yield the desired bound in the fixed-k regime.Source: §7 · p. 20
• High-girth graphs retain finite branching and unique short geodesics while removing the cube’s coordinate labels and vector-space structure.This setting is not a formal reduction of the cube conjectures, but it may support new local lower-bound techniques.Source: §7 · p. 20
• A technique proving the high-girth conjecture and applying to the cube would provide the kind of new lower-bound method sought by the paper.Source: §7 · p. 20

• The authors report that AI tools were used for copy-editing tasks only.Source: AI disclosure · p. 20