Lemma 6.3 — Cofactor argument removes the bottom fan-in bound
OpenParityBarrier563.Trilinear.Supplement.lemma_6_3boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , integers , , a test , real and be given. Suppose that for every restriction τ fixing at most R coordinates and every layered depth-d circuit C of size at most s whose restricted bottom fan-in is at most k, . Then every layered depth-d circuit C of size at most s satisfies
Restricted fan-in counts only live literals. This removes the bottom fan-in bound using hypotheses on every allowed cofactor.
Differences from the source:
- encoding: layered circuits and their restricted bottom fan-in → a layering of the published DAG with a live-literal wire count; reason: constants and fixed literals are omitted from fan-in while every actual gate is counted
- 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 set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 6.3: every cofactor of at most R fixed bits, and real fan-in bounds k. -/
theorem lemma_6_3 (N d s R : ℕ) (hd : 1 ≤ d) (hs : 1 ≤ s) (hR : R ≤ N)
(ψ : RealFn (Fin N)) (hψ : BoundedTest ψ) (k γ : ℝ)
(hk : 2*Real.logb 2 (4*s) ≤ k) (hγ : 0 ≤ γ)
(hcofactor : ∀ (τ : Restriction (Fin N)), fixedCount τ ≤ R →
∀ (C : Circuit (Fin N)) (L : Layering C d), C.size ≤ s → BottomBound L τ k →
|avg (fun z => restrict τ ψ z * ind (restrict τ C.eval) z)| ≤ γ) :
∀ (C : Circuit (Fin N)) (L : Layering C d), C.size ≤ s →
|avg (fun x => ψ x * ind C.eval x)| ≤ 2*γ + (2 : ℝ)^(-(R : ℝ)/2) := 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.3, printed p.27 / PDF p.29