The parameter
DefinitionAvgPHETH_Supplement_RParaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For and ,
where . Each level of a selector tree shortens the index length by the factor .
Formalization Note is , and is a real number.
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_gPar namespace AvgPHETH.Supplement /-- The parameter `R(n) = g(n) · log n` 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, "Parameters", p.39 (PDF 41)). `log` is `log₂`. -/ noncomputable def RPar (ε : ℕ → ℝ) (n : ℕ) : ℝ := (gPar ε n : ℝ) * Real.logb 2 n 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, "Parameters", p.39 (PDF 41)