The diagonalization clock
DefinitionAvgPHETH_Supplement_OracleData_tParaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For the -th triple of the enumeration,
The running time and the witness length of are capped to when diagonalizing.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_OracleData
import Definitions.Def_AvgPHETH_Supplement_IsActive
import Definitions.Def_AvgPHETH_Supplement_aPar
namespace AvgPHETH.Supplement
/-- The clock `t_s(n) = max{n, 2^{⌊a_{k_s}(n)/m_s⌋}}` if `(k_s, n)` is active, and `t_s(n) = n` otherwise,
to which the running time and the witness length of `M_s` are capped when diagonalizing
(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)). -/
noncomputable def OracleData.tPar (D : OracleData) (s n : ℕ) : ℕ := by
classical
exact
if IsActive D.eps (D.enum s).1 n then max n (2 ^ (aPar D.eps (D.enum s).1 n / (D.enum s).2.2))
else 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, "The construction", p.40 (PDF 42)