Active pairs
DefinitionAvgPHETH_Supplement_IsActiveaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
A pair of natural numbers is active if
where . The oracle stores a selector tree for the input exactly when is active; for every fixed all sufficiently large are active.
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_RPar namespace AvgPHETH.Supplement /-- The pair `(k, n)` is **active**: `k ≥ 1`, `n ≥ 16` and `R(n)^k ≤ √n` (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)). -/ def IsActive (ε : ℕ → ℝ) (k n : ℕ) : Prop := 1 ≤ k ∧ 16 ≤ n ∧ RPar ε n ^ k ≤ Real.sqrt 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)