The final assignment to the construction variables
DefinitionAvgPHETH_Supplement_OracleData_finalAsgaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
Every variable of the group is set by the completion stage and is not changed afterwards. This definition is the resulting total assignment; it determines every selector tree and hence the oracle .
Formalization Note Names that are not construction variables get the empty string, which no oracle answer reads.
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_OracleData_build import Definitions.Def_AvgPHETH_Supplement_OracleData_compStage namespace AvgPHETH.Supplement /-- The final assignment to the construction variables: a variable of the group `(k, n)` has the value it holds after the completion stage `D(k, n)` of its group, "by which all variables in the group are set" (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, p.40 (PDF 42)). It determines every selector tree `T^k_x`, hence `V`. **Formalization Note** A value assigned at some stage is never changed later. Names that are not construction variables get the empty string, which no oracle answer reads. -/ noncomputable def OracleData.finalAsg (D : OracleData) (U : ℕ → CVar → ℕ → ℝ) (v : CVar) : List Bool := ((D.build U (D.compStage v.k v.x.length)).1 v).getD [] 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, "The construction", p.40 (PDF 42)