Conditional seed averages and Bernoulli sumsets
DefinitionParityBarrier563_Trilinear_Supplement_SeedAndSubsetboolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Split a restriction τ of the published trilinear inputs into its data and seed parts. Average uniformly over all extensions a of the seed part and then independently draw a q-random restriction φ of remaining data bits:
The conditioning is a nonempty finite cube of live seed assignments, with no division by an event probability. For a finite available set B of nonnegative integer positions, subsetProb assigns T⊆B product weight . The sumset is , with ordinary integer addition. These definitions implement the distributions in Lemmas 6.5 and 6.6, including empty available sets.
Definition code
import Mathlib
import Definitions.Def_ParityBarrier563_Trilinear_TrilinearFunction
import Definitions.Def_ParityBarrier563_Trilinear_Correlation
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_FiniteAverages
set_option autoImplicit false
open scoped Classical
namespace ParityBarrier563.Trilinear.Supplement
/-- The data part and seed part of one restriction of all trilinear inputs. -/
def dataRestriction {n : ℕ} (τ : Restriction (TriVar n)) : Restriction (SliceVar n) :=
fun v => τ (.inl v)
def seedRestriction {n : ℕ} (τ : Restriction (TriVar n)) : Restriction (Fin (2*n-1)) :=
fun i => τ (.inr i)
/-- Finite uniform mean over the nonempty cube of seed extensions, followed by an
independent q-random restriction of remaining data variables. -/
noncomputable def seedCorrelation {n : ℕ} (τ : Restriction (TriVar n)) (q : ℝ) (k : ℕ) : ℝ :=
avg (fun z =>
let a := fill (seedRestriction τ) z
restrExpect q (fun φ => corr k (restrict φ
(restrict (dataRestriction τ) (sgn (slice n a))))))
/-- Bernoulli product probability on subsets of available positions B. -/
noncomputable def subsetProb (B : Finset ℕ) (η : ℝ) (P : Finset ℕ → Prop) : ℝ :=
∑ T ∈ B.powerset, (if P T then 1 else 0) *
(∏ i ∈ B, if i ∈ T then η else 1-η)
/-- Integer sumset; natural coordinates embed into integers with the same additions
and cardinalities, including empty sets. -/
def sumset (A T : Finset ℕ) : Finset ℕ :=
(A.product T).image (fun ij => ij.1 + ij.2)
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), Lemmas 6.5–6.6, printed pp.28–29 / PDF 30–31