Source-linked AI summary
Top-Down Lower Bounds for All Depths
Oliver Korten
TL;DR
Communication-based proofs had not yielded interesting lower bounds for non-monotone circuits at arbitrary depth, despite prior top-down results through depth 4. This paper maintains combinatorial invariants on communication rectangles and proves that depth-d protocols for Parity require cost above a threshold proportional to n^(1/(d−1)).
Problem
Communication-based arguments had not produced interesting lower bounds for non-monotone circuits beyond the depth-4 top-down results, leaving arbitrary depth open.
Source: §1 · p. 2Method
The proof maintains rectangle invariants that make the two input sets hard to distinguish on random small coordinate sets, using mirror-set and related lemmas to advance the adversary.
Source: §2.1 · p. 5, §2.2 · p. 8Results
For each d ≥ 2, KW(Parity_n) has no d-round protocol of cost m ≤ ε_d n^(1/(d−1)) for sufficiently large n.
Source: §4 · p. 15Takeaways & Limitations
The authors hope this top-down proof may help transfer ideas from monotone circuit complexity to non-monotone lower bounds, while its relevance to PHcc remains uncertain.
Source: §1 · p. 2The paper does not establish whether its ideas will help future PHcc lower bounds; the authors say that their role is unknown.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We prove that Parity requires $2^{n^{\Omega(1)}}$ size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds for circuits of depth 3 and 4. We first present a proof of a lower bound $\exp(n^{3^{-d}})$. In this case, nearly all of the relevant combinatorial ideas necessary for the proof are already present in some form in [GRSS24]. We then present two extensions of this argument, the first achieving a lower bound $\exp(\epsilon_d n^{1/(2d-2)})$ for some $\epsilon_d>0$ depending only on $d$, and the second achieving the essentially tight lower bound $\exp(\epsilon_d n^{1/(d-1)})$. These improved results each hinge on establishing a key lemma which quantifies the extent to which a high entropy random variable in $\{0,1\}^n$ will look close to uniform after projecting it onto a random small set of coordinates $R \subseteq [n]$.
1 Introduction
The introduction frames arbitrary-depth top-down lower bounds for Parity as the open continuation of work that had reached depth 4. It defines the communication-adversary viewpoint and previews progressively stronger bounds and the division of work between the author and GPT-6 Astra.
1 Introduction
- Top-down communication arguments had established exponential Parity lower bounds through depth 4, leaving greater fixed depths open until this work completed the program.The project began with and continued through.Source: §1 · p. 2
- The authors hope top-down proofs may help transfer ideas from monotone circuit complexity to non-monotone circuits, including possible progress on the KRW conjecture and PHcc lower bounds.They note that random-restriction arguments appear unavailable for PHcc, but say the role of these ideas in future lower bounds is unknown.Source: §1 · p. 2
1.1 KW Games and Adversaries:
- A KW game asks Alice and Bob, given inputs from disjoint sets, to communicate an index where their strings differ; circuit depth corresponds to protocol rounds and message cost.The correspondence for depth-d De Morgan circuits and d-round protocols is stated in.Source: §1.1 · p. 2
1.2 What Exactly Constitutes a “Top-Down” Proof?
- A “top-down proof” maintains a simple combinatorial invariant on the current rectangle to directly choose the communication adversary’s next move, rather than deriving it through a nonconstructive contradiction.The rectangle path corresponds to moving from a circuit output gate down toward a literal leaf.Source: §1.2 · p. 3
1.3 Notation:
- The notation defines min-entropy deficit for random variables and sets, with a set’s deficit equal to n minus its log-size.The paper also uses P ⊆p I for a random subset formed by independently including each coordinate with probability p.Source: §1.3 · pp. 3–4
1.4 Roadmap and AI Methodology
- The paper presents depth-d lower bounds in sequence: exp(n^(3−d)), exp(ε_d n^(1/(2d−2))), then exp(ε_d n^(1/(d−1))), tight up to ε_d.GPT-6 Astra autonomously generated the Section 2 result; the author developed the Section 3 extension and guided the strengthened lemma used for the Section 4 result, with machine assistance on its proof.Source: §1.4 · p. 4
2 The Initial Lower Bound
The initial lower bound for Parity is proved through a top-down communication adversary that maintains a rectangle invariant across protocol rounds. Its key step, the mirror set lemma, transfers a p-limit condition between the rectangle’s sides while controlling min-entropy deficit.
2.1 The Adversary
- Theorem 1 rules out d-round KW(Parity_n) protocols of cost m ≤ n^(3^-d), yielding the initial depth-d circuit lower bound.The theorem states the result for n ≥ 64^(3d).Source: §2 · p. 4, §2.1 · p. 5
- The adversary maintains large rectangle sides and a p-limit condition, which informally makes the two sets hard to distinguish using a random small coordinate set.After a protocol message, it selects a subrectangle that satisfies a quantitatively weaker version of the invariant.Source: §2.1 · p. 5
- The mirror set lemma converts a left-side p-limit condition into a right-side q-limit condition, where q = 64kp, while bounding the mirror set’s deficit by k + 2pn + 2.It assumes D∞(X) ≤ k and q ≤ 1.Source: §2.1 · p. 5
2.2 Proof of the Mirror Set Lemma
- A guided random step chooses y = g(x, P) among P-neighbors of x, landing in Y with probability at least 3/4 and producing an output that is often a q-limit of X.The proof also establishes H∞(Y^g) ≥ n − k − 2pn, allowing many such outputs in Y to be retained in the mirror set.Source: §2.2 · p. 8
- The probabilistic step asks whether every P-neighbor of a sampled x has a Q-neighbor in X, relating failure to whether X_{x,P∪Q} shatters P\Q.Conditioned on P∪Q = S, P\Q is sampled within S; the shattering lemma bounds failure using the average deficit of X_{x,S}.Source: §2.2 · pp. 7, 9
3 A Stronger Lower Bound
The section strengthens the top-down lower bound by replacing shattering with a light-patterns result for random coordinate projections. Its strong mirror-set lemma yields a depth-d Parity circuit wire lower bound of more than 2^{ε_d n^{1/(2d−2)}}.
3 A Stronger Lower Bound
- The earlier mirror-set extension fails because D∞(Y) cannot be bounded from k alone, even when D∞(X) ≤ k and every element of X is a p-limit of Y.The revised (p, k)-limit condition requires typical subcubes around a limit point to contain a substantial fraction of Y; under it, D∞(Y) ≤ O(k).Source: §3 · p. 10
- The strong mirror-set lemma turns a left (p, k)-limit condition and D∞(X) ≤ k into a subset Y′ of deficit at most 2k + 2 satisfying a right (Ck²p, 65k)-limit condition.The proof samples from large guiding sets and establishes both high min-entropy and a limit condition for the resulting random variable.Source: §3 · pp. 10–11
- The argument obtains a subset of Y with deficit O(k) consisting of (O(k²p), O(k))-limits of X, yielding a bound exp(n^(1/(2d-2))) rather than exp(n^(1/(d-1))).Source: §3 · p. 10
- For every d ≥ 2, depth-d circuits computing Parity_n require more than 2^{ε_d n^{1/(2d−2)}} wires for sufficiently large n.Equivalently, KW(Parity_n) has no d-round protocol of cost m ≤ ε_d n^{1/(2d−2)}.Source: §3 · p. 12
3.1 Random Projections of a Dense Set Are Close to Uniform
- With probability at least 1 − O(rD∞(X)), a random projection has support equal to the full cube and Shannon entropy at least |R| − 0.1.These are distinct notions of closeness to uniformity: full support and near-maximal Shannon entropy.Source: §3.1 · pp. 12–13
- The uniformity lemma bounds the normalized L_t distance of a random projection’s probability mass function from uniform for most coordinate sets, in the regime rD∞(X)² ≪ 1.Its proof combines hypercontractivity, r-spreadness, and the level-ℓ inequality.Source: §3.1 · pp. 13–14
4 A Nearly Tight Lower Bound
The section proves a near-tight lower bound for depth-d circuits computing Parity using an improved light-pattern lemma and analytic inequalities for the harmonic mean transform.
4 A Nearly Tight Lower Bound
- For each d ≥ 2, protocols for KW(Parity_n) require cost greater than ε_d n^(1/(d−1)), yielding more than 2^(ε_d n^(1/(d−1))) wires for depth-d Parity circuits.The theorem assumes sufficiently large n and ε_d > 0 depending only on d.Source: §4 · p. 15
- The improved light-pattern lemma allows r ≤ (Ck)^−1 rather than (Ck)^−2, while restricting light patterns to probabilities at most 2^-2k-2 relative to uniform.The text says this restriction costs nothing in the application to Theorem 3.Source: §4 · p. 15
- The proof recasts a projection bound for the renormalized distribution as a lower bound on its harmonic mean transform, then derives the lemma using Markov's inequality.The transform is introduced for functions on the hypercube and coordinate sets.Source: §4 · pp. 15–16
- The transform is concave, and the proof uses concavity while inductively splitting the function according to its last coordinate.The induction applies the one-coordinate case to the two slices and then the inductive hypothesis.Source: §4 · pp. 16–17
- A transfer principle for downward-closed families carries the bound to sparse random coordinate sets, with the proof targeting membership probability at least 2^−k/2−1 at sampling rate 1/4.The argument identifies sets where the transform exceeds 2^−k−2 as a downward-closed family.Source: §4 · p. 18