The induced value of a selector tree
DefinitionAvgPHETH_Supplement_treeValaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let an assignment give every root bit and every selector a value. The selector tree has and, for a node at depth with index among its siblings,
This definition is the induced value at the node . For a leaf it is the answer of the oracle. The child selected by has value and every other child has the neutral value of the gate of , so the AND-rooted alternating tree evaluates to its root bit on the induced leaf values, and that leaf assignment is critical.
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_treeValFrom namespace AvgPHETH.Supplement /-- The induced value `T^k_x(y₁, …, y_j)` at the node `(y₁, …, y_j)` of the selector tree `T^k_x` whose root bit and selectors are given by the assignment `β` (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), Definition 8.1, p.38 (PDF 40)): `T(root) = B`, and for a node `v` at depth `j ≥ 1` with index `y` among its siblings, `T(v) = T(parent(v)) ∨ 1[y ≠ S(parent(v))]` if `j` is odd and `T(v) = T(parent(v)) ∧ 1[y = S(parent(v))]` if `j` is even. For a leaf this is the answer `V_k(x, y₁, …, y_k)` (§8.1, p.39 (PDF 41)). **Formalization Note** The root bit is `1` iff the value of `B^k_x` is the one-bit string `[true]`. -/ def treeVal (β : CVar → List Bool) (k : ℕ) (x : List Bool) (ys : List (List Bool)) : Bool := treeValFrom β k x [] (decide (β ⟨k, x, true, []⟩ = [true])) ys 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…), Definition 8.1, p.38 (PDF 40)