Lemma 6.1 — Decision trees with CNF/DNF leaves have bounded CNF norm
OpenParityBarrier563.Trilinear.Supplement.lemma_6_1boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let V be any finite variable set, and integers. Suppose F is computed by a binary decision tree of depth at most R with a k-CNF or k-DNF at each leaf, evaluated on the input reaching that leaf. Then
Leaf types may be mixed and R=0 is included. A leaf need agree with F only on its path subcube. This controls the CNF norm of partial decision trees.
Differences from the source:
- encoding: decision tree with leaf functions on path subcubes → an inductive finite LeafTree with eval equal to F; reason: the reached leaf alone determines the output, preserving all path-subcube instances
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_DecisionTree import Definitions.Def_ParityBarrier563_Trilinear_Correlation set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 6.1: R=0 and mixed CNF/DNF leaves are allowed. -/
theorem lemma_6_1 (V : Type) [Fintype V] [DecidableEq V]
(k R : ℕ) (hk : 1 ≤ k) (F : BoolFn V) (T : LeafTree V)
(hdepth : T.depth ≤ R) (hleaves : T.GoodLeaves k) (hF : T.eval = F) :
sizeB k (ind F) ≤ (2 : ℝ)^(R+1) := 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.1, printed p.26 / PDF p.28