The exponent of the restriction probability
DefinitionAvgPHETH_Supplement_pExpaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For the random restrictions of the oracle construction use the probability
This definition is its exponent .
Formalization Note Only the exponent is stored: a -random restriction of variables leaves of them unset.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_aPar
import Definitions.Def_AvgPHETH_Supplement_gPar
namespace AvgPHETH.Supplement
/-- The exponent `⌈a_{j+1}(n) · g(n)^{1/2}⌉` of the restriction probability
`p_j(n) = 2^{−⌈a_{j+1}(n) g(n)^{1/2}⌉}`, for `0 ≤ j < k`
(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 3, p.39 (PDF 41)).
**Formalization Note** Only the exponent is stored: a `p_j`-random restriction of `N` variables leaves
`⌊p_j N⌋ = N / 2^{pExp}` (natural-number division) of them unset. -/
noncomputable def pExp (ε : ℕ → ℝ) (j n : ℕ) : ℕ :=
⌈(aPar ε (j + 1) n : ℝ) * Real.sqrt (gPar ε 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), item 3