Theorem 5.6 — Hashed polynomial evaluation: lower bound for every constant depth
OpenParityBarrier563.Trilinear.Supplement.theorem_5_6boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed integer there exist and such that for every and every input length , every depth-at-most-d circuit C computing the entire padded hashed polynomial evaluation function satisfies
The hash, every monic modulus P of degree and all polynomial coefficients are input bits; trailing bits are ignored. Constants depend only on d and are uniform in the padding. This covers the full evaluator, beyond any selected hard slice.
Differences from the source:
- encoding: asymptotic gate bound and sufficiently large n → positive constants and a threshold before n, padding and 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_HashedEvaluation import Definitions.Def_ParityBarrier563_Trilinear_Circuit set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Theorem 5.6, every padded input length and all monic input moduli. -/
theorem theorem_5_6 (d : ℕ) (hd : 3 ≤ d) :
∃ (c : ℝ) (N : ℕ), 0 < c ∧ 64 ≤ N ∧ ∀ n : ℕ, N ≤ n →
∀ (padding : Fin 5) (C : Circuit (Fin (5*n+padding.val))),
C.depth ≤ d → C.Computes (hashedFn n padding) →
(2 : ℝ)^(c*((n : ℝ)*Real.logb 2 n)^(1/((d : ℝ)-1))) ≤ C.size := 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 5.6, printed p.20 / PDF p.22