Lemma 6.2 — Both depth-two restriction bounds for layered circuits
OpenParityBarrier563.Trilinear.Supplement.lemma_6_2boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an integer . There exist functions k(s),q(s), positive comparison constants and , depending only on d, with , , and for every integer . For every finite variable set V, every layered depth-d circuit C of size at most s and bottom fan-in at most , every and integer , let for a q(s)-random restriction. Both estimates hold:
The same k,q work before choosing V,C,ψ,D. This is the depth-two reduction needed for average-case bounds.
Differences from the source:
- encoding: Θ_d parameters and O_d exponent → positive comparison constants, functions k(s),q(s), and A before s,V,C,ψ,D; reason: this spells out the source uniformity and both estimates for one choice of parameters
- encoding: alternating layered circuits, with actual gate count and the stated fan-in bounds → Layering data over the published Circuit DAG, retaining constants and unary gates and counting literal or gate wires; reason: this is the source layer convention and keeps both output types; duplicate wires can be deleted without increasing any bound
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_Layering import Definitions.Def_ParityBarrier563_Trilinear_Correlation set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 6.2: one choice of k(s),q(s) works for both estimates and every test and D. -/
theorem lemma_6_2 (d : ℕ) (hd : 3 ≤ d) :
∃ (ak bk aq bq A : ℝ) (k : ℕ → ℕ) (q : ℕ → ℝ),
0 < ak ∧ 0 < bk ∧ 0 < aq ∧ 0 < bq ∧ 0 < A ∧
∀ s : ℕ, 2 ≤ s →
1 ≤ k s ∧ 0 < q s ∧ q s ≤ 1 ∧
ak*Real.logb 2 s ≤ k s ∧ (k s : ℝ) ≤ bk*Real.logb 2 s ∧
aq*(Real.logb 2 s)^(d-2) ≤ 1/q s ∧
1/q s ≤ bq*(Real.logb 2 s)^(d-2) ∧
∀ (V : Type) [Fintype V] [DecidableEq V] (C : Circuit V) (L : Layering C d),
C.size ≤ s → BottomBoundFull L (3*Real.logb 2 (4*s)) →
∀ (ψ : RealFn V), BoundedTest ψ → ∀ D : ℕ, 1 ≤ D →
let E := restrExpect (q s) (fun φ => corr (k s) (restrict φ ψ))
|avg (fun x => ψ x * ind C.eval x)| ≤ (d : ℝ)/(s : ℝ)^3 + 2*E ∧
|avg (fun x => ψ x * ind C.eval x)| ≤
(s : ℝ)^A * (2 : ℝ)^(-(D : ℝ)) +
(2 : ℝ)^((2 : ℕ)^(d-2)*D) * E := by sorry
end ParityBarrier563.Trilinear.Supplement
Source
Nikolai Chukhin, Xin Li, Ivan Mihajlin, Yan Zhong, Breaking the Parity Barrier for Constant-Depth Circuits, STOC 2027 submission #563 (October 2026), Lemma 6.2, printed p.26 / PDF p.28