The completion deadline
DefinitionAvgPHETH_Supplement_JParaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For ,
It is the stage by which the variables of a reserved group , which determine the answers of on inputs of length , are completely assigned.
Formalization Note is . For an active pair, .
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_aPar namespace AvgPHETH.Supplement /-- The completion deadline `J_k(n) = ⌈(log a_k(n))/4⌉ + 4` (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", item 4, p.39 (PDF 41)). `log` is `log₂`. **Formalization Note** For active `(k, n)`, `a_k(n) ≥ ⌊√n⌋ ≥ 4`, so the logarithm is of a number `≥ 4`. -/ noncomputable def JPar (ε : ℕ → ℝ) (k n : ℕ) : ℕ := ⌈Real.logb 2 (aPar ε k n) / 4⌉₊ + 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, "Parameters", p.39 (PDF 41), item 4