The alphabet of a construction variable
DefinitionAvgPHETH_Supplement_CVar_valLenaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
A root bit takes values in , strings of length . A selector at depth , , takes values in : it names one of the children of its node.
This definition is the length of the value: for a root bit and for a selector at depth .
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_CVar
import Definitions.Def_AvgPHETH_Supplement_aPar
namespace AvgPHETH.Supplement
/-- The length of the value of a construction variable: `1` for a root bit `B^k_x` (alphabet `{0,1}`),
and `a_{j+1}(|x|)` for a selector at depth `j` (alphabet `Y_{j+1}(|x|) = {0,1}^{a_{j+1}(|x|)}`)
(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, "Construction variables", p.39 (PDF 41)). -/
noncomputable def CVar.valLen (ε : ℕ → ℝ) (v : CVar) : ℕ :=
if v.isBit = true then 1 else aPar ε (v.path.length + 1) v.x.length
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, "Construction variables", p.39 (PDF 41)