The language
DefinitionAvgPHETH_Supplement_Lkaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For the oracle and ,
, and it is the language shown to be hard for machines. Since the quantified expression evaluates the selector tree , iff the root bit is .
Formalization Note is the induced leaf value under the assignment that determines .
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_treeVal
import Definitions.Def_AvgPHETH_Supplement_IsActive
import Definitions.Def_AvgPHETH_Supplement_aPar
import Definitions.Def_AvgPHETH_AltLen
namespace AvgPHETH.Supplement
open AvgPHETH
/-- The language `L_k^O` (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, p.39 (PDF 41)):
`x ∈ L_k^O ⟺ (k, |x|)` is active and
`∀y₁ ∈ Y₁(|x|) ∃y₂ ∈ Y₂(|x|) ⋯ Q_k y_k ∈ Y_k(|x|) : V_k(x, y₁, …, y_k) = 1`.
**Formalization Note** `β` is the assignment to the construction variables that determines `V`, and
`V_k(x, y₁, …, y_k) = T^k_x(y₁, …, y_k)` is `treeVal β k x [y₁, …, y_k]`; `Y_j(n) = {0,1}^{a_j(n)}`. The
quantifiers are the published `AvgPHETH.AltLen` with first quantifier `∀`. -/
def Lk (ε : ℕ → ℝ) (β : CVar → List Bool) (k : ℕ) : Set (List Bool) :=
{x | IsActive ε k x.length ∧
AltLen ((List.range k).map (fun j => aPar ε (j + 1) x.length)) false
(fun ys => treeVal β k x ys = true)}
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, p.39 (PDF 41)