Theorem 1.6 — Trilinear upper bound at every constant depth
OpenParityBarrier563.Trilinear.Supplement.theorem_1_6boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed integer there exist and such that for every the complete trilinear function has an AND/OR circuit C with
The circuit reads all input coordinates, including the seed block. Constants depend only on d. This companion upper bound complements the published goal's lower bound.
Differences from the source:
- encoding: asymptotic circuit-existence upper bound → positive A_d and a threshold before n and the existential circuit; reason: this spells out the source bound at full strength, with exactly its allowed dependence
- encoding: the complete input cube and depth-d AND/OR circuits → the published coordinate types and Circuit, with depth at most d; agreement is a finite uniform probability where used; reason: all blocks remain in the cube, fan-in and fan-out are unrestricted, and size is the number of gates
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_FiniteAverages import Definitions.Def_ParityBarrier563_Trilinear_Circuit import Definitions.Def_ParityBarrier563_Trilinear_TrilinearFunction set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Theorem 1.6: existence on the whole trilinear cube, including its seed block. -/
theorem theorem_1_6 (d : ℕ) (hd : 3 ≤ d) :
∃ (A : ℝ) (N : ℕ), 0 < A ∧ 1 ≤ N ∧ ∀ n : ℕ, N ≤ n →
∃ C : Circuit (TriVar n), C.depth ≤ d ∧ C.Computes (trilinearFn n) ∧
(C.size : ℝ) ≤ (2 : ℝ)^(A*(n : ℝ)^(2/(d : ℝ))) := 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), Theorem 1.6, printed p.4 / PDF p.6