Layered alternating formulas of depth
DefinitionAvgPHETH_Supplement_Formula_IsLayeredAltcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
A formula is a layered alternating formula of depth , AND-rooted or OR-rooted, if gate types alternate between consecutive levels, every root-to-leaf path contains exactly gates, and the root is an AND gate (respectively an OR gate). A formula of depth is a single leaf.
These are the hard formulas of Theorem 7.1.
Formalization Note Every internal node is required to have at least one child, as internal nodes of a tree do.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_Formula
namespace AvgPHETH.Supplement
/-- `F.IsLayeredAlt b d`: `F` is a layered alternating AND-OR formula of depth `d` whose root is an
AND gate if `b = true` and an OR gate if `b = false` (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §4.3, p.16 (PDF 18)): gate types
alternate between consecutive levels, every internal node has at least one child, and every
root-to-leaf path contains exactly `d` gates.
**Formalization Note** A formula of depth `0` is a single leaf (its root type is not used). -/
def Formula.IsLayeredAlt {V : Type} : Formula V → Bool → ℕ → Prop
| .leaf _, _, 0 => True
| .gate a m ch, b, d + 1 => a = b ∧ 1 ≤ m ∧ ∀ i, (ch i).IsLayeredAlt (!b) d
| _, _, _ => False
end AvgPHETH.Supplement
Source
Hirahara–Juvekar–Nanashima, Average-Case Hardness of PH from ETH-Type Hypotheses, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §4.3, p.16 (PDF 18)