Theorem 6.2 —
OpenAvgPHETH.Supplement.theorem_6_2average-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose for an oracle and a fixed . Then, for every ,
Each additional symmetric-alternation operator saves a logarithmic factor in the exponent. With Lemma 6.5 this gives Theorem 1.2 (ii).
Differences from the source:
- encoding: → witnessTime c (k+1) id, i.e. , with a natural chosen after ; reason: only excludes ; the published S2kTIME already allows a constant factor and summand
- encoding: of §4.2 → the published AvgPHETH.S2kTIME; reason: the base mission's definition of the same class
Preamble
import Mathlib import Definitions.Def_AvgPHETH_DistSubAvgP import Definitions.Def_AvgPHETH_SigmaPO import Definitions.Def_AvgPHETH_S2kTIME import Definitions.Def_AvgPHETH_witnessTime
Formal statement
namespace AvgPHETH.Supplement
open AvgPHETH
/-- **Theorem 6.2** (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.26 (PDF 28)): suppose `DistΣ_{d+1}^{p,O} ⊆ AvgP^O` for an oracle `O` and a
fixed `d ≥ 1`. Then, for every `k ≥ 0`, `Σ_d^{p,O} ⊆ S₂^kTIME^O[2^{O(n/log^{k+1} n)}]`.
**Formalization Note** `S₂^kTIME^O[·]` is the published `AvgPHETH.S2kTIME` (which already allows a
constant factor and summand); `2^{O(n/log^{k+1} n)}` is `witnessTime c (k+1) id`, i.e.
`⌈2^{c n/(log₂ max(n,2))^{k+1}}⌉`, for a constant `c` chosen after `L`. -/
theorem theorem_6_2 (O : Set (List Bool)) (d : ℕ) (hd : 1 ≤ d) (hAvg : DistSubAvgP O (d + 1))
(k : ℕ) (L : Set (List Bool)) (hL : L ∈ SigmaPO O d) :
∃ c : ℕ, S2kTIME O k (witnessTime c (k + 1) id) L := 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 6.2, p.26 (PDF 28)