The state of the construction after stages
DefinitionAvgPHETH_Supplement_OracleData_buildaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
The oracle construction proceeds in stages . This definition is its state after the first stages: the partial assignment to the construction variables and the table of -answers. Before stage nothing is assigned.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_OracleData_stage
namespace AvgPHETH.Supplement
/-- The state `(ρ, tab)` of the oracle construction after its first `i` stages: the partial assignment
to the construction variables and the table of `A`-answers
(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, pp.40–41 (PDF 42–43)). Before stage `1` nothing is assigned.
**Formalization Note** `U i v c` is the seed of the variable `v`, channel `c`, in the restriction round
of stage `i` (stages are numbered from `1`). -/
noncomputable def OracleData.build (D : OracleData) (U : ℕ → CVar → ℕ → ℝ) :
ℕ → (CVar → Option (List Bool)) × (ℕ → ℕ → List Bool → ℕ → Option Bool)
| 0 => (fun _ => none, fun _ _ _ _ => none)
| i + 1 => D.stage (U (i + 1)) (i + 1) (D.build U i)
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, pp.40–41 (PDF 42–43)