The completion stage of a group
DefinitionAvgPHETH_Supplement_OracleData_compStageaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
The pairs are reserved for diagonalization. The completion stage of a group is
All variables of the group are set by stage .
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_OracleData import Definitions.Def_AvgPHETH_Supplement_JPar namespace AvgPHETH.Supplement /-- The completion stage `D(k, n)` of the group `(k, n)`: `J_k(n)` if `(k, n)` is reserved, i.e. `(k, n) = (k_s, n_s)` for some `s`, and `1` otherwise (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)). -/ noncomputable def OracleData.compStage (D : OracleData) (k n : ℕ) : ℕ := by classical exact if ∃ s, (D.enum s).1 = k ∧ D.ns s = n then JPar D.eps k n else 1 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)