Names of the construction variables , ,
DefinitionAvgPHETH_Supplement_CVaraverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
The selector trees of the oracle construction are determined by variables: for a string and , the root bit over , the root selector over , and, for each internal node of the selector tree with , the selector over .
This type consists of the names of such variables: a level , a string , a flag saying whether the variable is a root bit, and the node (empty for the root).
Formalization Note The names that are variables of the construction are singled out by a separate validity predicate. Every value is stored as a binary string: a root bit as the one-bit string , a selector as an element of .
Definition code
import Mathlib
namespace AvgPHETH.Supplement
/-- A (name of a) **construction variable** of the oracle construction
(Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §8.1, "Construction variables", p.39 (PDF 41)): for a string `x` and `k ≥ 1`,
the root bit `B^k_x` is `⟨k, x, true, []⟩`, the root selector `S^k_x` is `⟨k, x, false, []⟩`, and the
selector `S^k_{x,y₁,…,y_j}` of the internal node `(y₁, …, y_j)` of the selector tree `T^k_x` is
`⟨k, x, false, [y₁, …, y_j]⟩`.
**Formalization Note** This is the type of all such names; the ones that are variables of the
construction (active `(k, |x|)`, a path of the right shape) are singled out by `CVar.IsValid`. Every
value of a variable is stored as a binary string: a root bit `b` as the one-bit string `[b]`, a selector
over `Y_{j+1} = {0,1}^{a_{j+1}(n)}` as that string. -/
structure CVar where
/-- the level `k` of the oracle `V_k` -/
k : ℕ
/-- the input `x` whose selector tree `T^k_x` the variable belongs to -/
x : List Bool
/-- `true` for the root bit `B^k_x`, `false` for a selector -/
isBit : Bool
/-- the node `(y₁, …, y_j)` whose selector this is (`[]` for the root, and for the root bit) -/
path : List (List Bool)
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…), §8.1, "Construction variables", p.39 (PDF 41)