The stage of an -query
DefinitionAvgPHETH_Supplement_stageOfaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a time parameter ,
All queries to the help oracle with time parameter are assigned in stage of the construction.
Formalization Note is . Valid queries have , where .
Definition code
import Mathlib
namespace AvgPHETH.Supplement
/-- The stage `i(T) = max{1, ⌊(log log T)/4⌋}` in which the `A`-queries with time parameter `T` are
assigned (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)). `log` is `log₂`.
**Formalization Note** Valid `A`-queries have `T ≥ 2`, where `log log T ≥ 0`. -/
noncomputable def stageOf (T : ℕ) : ℕ := max 1 ⌊Real.logb 2 (Real.logb 2 T) / 4⌋₊
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)