Theorem 8.7 — with probability one, for every
OpenAvgPHETH.Supplement.theorem_8_7average-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an efficiently computable function with and , let be the random oracle built from by the staged construction of Section 8.1, and let be the language of the inputs of active length with . Then, with probability one, simultaneously for every ,
Consequently,
So relative to a language needs time almost , which shows that the simulations of Theorem 1.2 cannot be improved by relativizing techniques.
Formalization Note The oracle is a function of the construction data and of independent uniform seeds; the statement is for all admissible data and seeds. Both conclusions, for all at once, hold for almost every .
Differences from the source:
- reading: the oracle of the construction of §8.1, whose enumeration , reserved lengths and lexicographic order are left to be chosen → for every choice: every enumeration of all triples with each appearing infinitely often, every sequence satisfying (a)–(d), every rule selecting one of the disagreeing pairs in step 3(b)iii; reason: the page fixes none of them; the statement is asserted for each admissible choice, which includes the page's
- reading: "an enumeration of all triples " and codes of machines → a numbering of oracle machines in which every machine occurs up to its acceptance behaviour (same accepting runs for every oracle, clock and input); and ; the statement holds for every such numbering; reason: the published machine model has arbitrary alphabet and state types, so its machines form a proper class and have no enumeration; the construction and both proofs use a machine only through its accepting runs
- reading: "efficiently computable", , " without loss of generality" (§8.1, p.38) → for all ; ; computable from in time ; for every , for all large ; reason: §8.1 fixes with these properties for the whole section; positivity is presupposed by ; the construction uses only through
- encoding: "with probability one" over the random restrictions of the construction → for almost every , for any family of independent seeds uniform on , one per stage, variable and channel, on any probability space; a restriction round is a deterministic function of its seeds and the current assignment (priorities choose the surviving subset, the other seeds the values); reason: conditionally on the earlier rounds this is the -random restriction of Definition 4.4, independently for each family, group and stage
- encoding: "an appropriate encoding" of -queries, an unspecified encoding of -queries and of the answer , and → -query ↦ binary tuple code of ; -query ↦ tuple code of , with iff and iff ; is the published join; reason: linear-time decodable encodings with valid -queries of length , as the page requires; they change no class
- encoding: oracle bits not yet fixed when (step 2(a)) and (step 3(b)) are formed → unassigned -queries are answered , unassigned variables of other groups get the empty string; reason: Proposition 8.3 shows these bits are never read within the clock, so the default changes nothing
- encoding: "lexicographically first possible value" / "lexicographically first valid assignment" → every unset variable of the group gets the all-zeros string of its alphabet; reason: the first element of in lexicographic order
- encoding: → for every with as , ; for every ; reason: the meaning of in a class bound; only large matter
- reading: for bounds that need not be time-constructible → SigmaKTime: for all , for some and machine ; reason: the characterisation of Definition 4.3 (p.15), which is how the proof on p.47 uses the class ("running time and witness length are each at most "); it contains the page's class for time-constructible , so the non-membership is at least as strong
- encoding: in the definition of ; ; → the induced leaf value of the final assignment; PiPO (complements of the published SigmaPO); , with the bound at ; reason: outputs exactly this value; two input lengths, absorbed by the threshold of SigmaKTime
Preamble
import Mathlib import Definitions.Def_AvgPHETH_Supplement_OracleData_oracle import Definitions.Def_AvgPHETH_Supplement_OracleData_Admissible import Definitions.Def_AvgPHETH_Supplement_Lk import Definitions.Def_AvgPHETH_Supplement_PiPO import Definitions.Def_AvgPHETH_Supplement_SigmaKTime
Formal statement
namespace AvgPHETH.Supplement
open AvgPHETH MeasureTheory Filter Asymptotics
/-- **Theorem 8.7** (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), p.47 (PDF 49)): "With probability one, simultaneously for
every `k ≥ 1`, `L_k^O ∉ Σ_kTIME^O[2^{o(a_k(n))}]`. Consequently,
`Π_k^{p,O} ⊄ Σ_kTIME^O[2^{ε(n)n/log^k n}]`", where `O = A + V` is the random oracle of the construction
of §8.1 (pp.38–41, PDF 40–43).
**Formalization Note** The oracle is `D.oracle` and `L_k^O` is `Lk` at the final assignment, for all
data and seeds satisfying `OracleData.Admissible`. "With probability one" is `∀ᵐ ω ∂μ`, and both
conclusions, for every `k ≥ 1`, are inside it. `L ∉ Σ_kTIME^O[2^{o(a_k(n))}]` is: `L ∉ Σ_kTIME^O[2^{f(n)}]`
for every `f : ℕ → ℝ` with `f = o(a_k)` as `n → ∞`. `log` is `log₂`; `Σ_kTIME^O[·]` is `SigmaKTime`,
whose threshold `⌈c·t⌉₊ + c` absorbs the lengths `n ≤ 1`, where `log₂ n = 0`. -/
theorem theorem_8_7 (D : OracleData) {Ω : Type} [MeasurableSpace Ω] (μ : MeasureTheory.Measure Ω)
[MeasureTheory.IsProbabilityMeasure μ] (U : ℕ × CVar × ℕ → Ω → ℝ) (hD : D.Admissible μ U) :
∀ᵐ ω ∂μ, ∀ k : ℕ, 1 ≤ k →
(∀ f : ℕ → ℝ, f =o[atTop] (fun n => (aPar D.eps k n : ℝ)) →
Lk D.eps (D.finalAsg (fun i v c => U (i, v, c) ω)) k ∉
SigmaKTime (D.oracle (fun i v c => U (i, v, c) ω)) k (fun n => (2 : ℝ) ^ f n)) ∧
∃ L ∈ PiPO (D.oracle (fun i v c => U (i, v, c) ω)) k,
L ∉ SigmaKTime (D.oracle (fun i v c => U (i, v, c) ω)) k
(fun n => (2 : ℝ) ^ (D.eps n * ((n : ℝ) / Real.logb 2 n ^ k))) := by sorry
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…), Theorem 8.7, p.47 (PDF 49); oracle construction of §8.1, pp.38–41 (PDF 40–43)