PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Gülce Kardeş, Benjamin Rossman

arXiv:2609.01759v1cs.CC

TL;DR

The paper asks whether top-down, local games can yield strong lower bounds beyond classical bottom-up AC^0 methods. It introduces the Chopping Game and applies polynomial approximation, then studies k-local parity games and high-girth graph analogues. It proves m ≥ n^Ω(k^(1/d)/d) for affine Spoiler strategies and conjectures super-polynomial lower bounds for unrestricted local games.

  • Problem

    Classical AC^0 lower bounds are predominantly bottom-up, motivating top-down and local formulations that may isolate new lower-bound questions.

  • Method

    The paper formalizes top-down arguments with the Chopping Game, applies polynomial approximation, and defines k-local and graph-theoretic variants.

  • Results

    Every d-round affine winning strategy in the k-local Chopping Game for parity requires m ≥ n^Ω(k^(1/d)/d), while the paper conjectures m = n^ω(1) for unrestricted d-round local protocols.

  • Takeaways & Limitations

    The Chopping Game gives a top-down implementation of the classical parity approximation lower bound and a framework for conjectured stronger local and graph-theoretic bounds.

  • Takeaways & Limitations

    The proved local lower bound relies on affine strategies and vector-space structure, while the approximation argument does not provide the desired bound in the fixed-k regime.

Abstract

from arXiv · show

Classical lower bounds for $\mathrm{AC^0}$ circuits proceed bottom-up by simplifying or approximating gates beginning at the input layer. We introduce a complementary top-down model called the Chopping Game, played by adversaries Spoiler and Duplicator on the sets of $0$- and $1$-inputs of a Boolean function. In each round, Spoiler keeps at least a $1/m$-fraction of one side, and Duplicator arbitrarily restricts the other; Spoiler seeks to minimize (and Duplicator to maximize) the number of rounds until some coordinate separates the two remaining sets. Every depth-$d$, fan-in-$m$ circuit induces a $d$-round winning strategy for Spoiler, while Duplicator strategies that survive $d$ rounds formalize top-down lower-bound arguments. Through the Chopping Game and using the polynomial-approximation method, we first obtain the classical lower bound for depth-$d$ $\mathrm{AC^0}$ circuits in a top-down fashion. We then consider a $k$-local variant of the Chopping Game, which relaxes Spoiler's win condition by requiring a separating coordinate within each Hamming ball of radius $k$, rather than a single coordinate globally. We put forward a conjecture that the $d$-round $k$-local Chopping Game for $\mathrm{PARITY}$ requires $m = n^{ω(1)}$ in the regime $d \ll k \ll n$. We prove such a lower bound $m \ge n^{Ω(k^{1/d}/d)}$ when Spoiler is restricted to so-called affine strategies, a class of strategies that achieves the best known upper bounds. Finally, we formulate a version of the $k$-local Chopping Game on $n$-regular graphs of girth $>2k$, and we conjecture a graph-theoretic analogue of ``$\mathrm{PARITY} \notin \mathrm{AC^0}$''.

1 Introduction

The paper introduces a top-down Chopping Game for AC^0 lower bounds, recovers the classical parity bound via polynomial approximation, and studies local variants with conjectured and proved complexity lower bounds.

  • 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.
  • The Chopping Game: 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.
  • 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).
  • 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.
  • Local games: 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.
  • 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.

2 Preliminaries

The preliminaries define AC^0 circuits and KW communication protocols, then recast protocol descent as Partition and Chopping Games. Partition exactly characterizes bounded-fan-in formulas, while Chopping weakens partition moves to obtain stronger lower-bound consequences.

  • 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.
  • 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.
  • Karchmer–Wigderson Games: 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.
  • 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.
  • Partition Game: 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.
  • 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.
  • Chopping Game: 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.
  • Chopping Game: 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.

3 Top-Down Approximation Theorems

A winning Chopping Game strategy yields weak separators through top-down polynomial and formula constructions. For parity, translation symmetry amplifies polynomial separation to constant advantage, recovering classical AC0 lower bounds; analogous formula separators yield sensitivity-based bounds.

  • 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.
  • 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.
  • Polynomial approximation: 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.
  • Polynomial approximation: 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)))).
  • 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.
  • Formula approximation: 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.

4 Local Karchmer–Wigderson and Chopping Games

The section defines local and exact-distance variants of KW and Chopping Games, then establishes tight two-round bounds and round-independent even-distance lower bounds. It conjectures super-polynomial fan-in lower bounds in the regime d ≪ k ≪ n.

  • 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.
  • 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⌉.
  • Two-round bounds: (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.
  • 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.
  • Even and odd distances: 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.
  • 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.

5 Lower Bound for Linear Protocols

The section reduces linear KW protocols and affine Chopping strategies to the exact-weight ELEMXF2 query problem. Round elimination yields lower bounds with exponents k^(1/(d−1)) for linear protocols and k^(1/d) for affine strategies, including the k-local consequence for parity.

  • 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.
  • Reduction framework: 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.
  • 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.
  • 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.
  • 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.

6 Graph-Theoretic Conjecture

The section formulates Distance-k communication and Chopping Games on finite high-girth regular graphs, where distance-k pairs have unique shortest paths. It gives coloring-based upper bounds, contrasts finite graphs with infinite trees, and proposes a graph-theoretic analogue of PARITY ∉ AC^0.

  • 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.
  • Graph relation: 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.
  • 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.
  • 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.
  • 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.
  • 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.

7 Future Directions

The paper identifies open lower-bound problems for unrestricted protocols and chopping strategies, and proposes high-girth graphs as a simplified setting for developing local methods.

  • The main open problem is proving m = n^ω(1) for the Distance-k KW and Distance-k Chopping Games when d ≪ k ≪ n.
  • 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) → ∞.
  • The approximation argument does not yield the desired bound in the fixed-k regime.
  • 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.
  • 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.

AI disclosure

The paper states that its definitions, results, and conjectures were developed, proved, and formulated by the authors, with AI tools used only for copy-editing.

  • The authors report that AI tools were used for copy-editing tasks only.
Loading 2609.01759v1…