The parameter
DefinitionAvgPHETH_Supplement_gParaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a function with positive values, the oracle construction of Section 8 uses the integer parameter
It measures how slowly tends to ; all other parameters of the construction are defined from it.
Formalization Note is . The natural-number ceiling is on negative reals, which the maximum with absorbs.
Definition code
import Mathlib
namespace AvgPHETH.Supplement
/-- The parameter `g(n) = max{16, ⌈log(1/ε(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)).
**Formalization Note** `log` is `log₂`. The natural-number ceiling `⌈·⌉₊` is `0` on negative reals,
which the maximum with `16` absorbs. `ε(n) > 0` is a hypothesis wherever `g` is used. -/
noncomputable def gPar (ε : ℕ → ℝ) (n : ℕ) : ℕ := max 16 ⌈Real.logb 2 (1 / ε 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)