Families of construction variables
DefinitionAvgPHETH_Supplement_CVar_SameFamilyaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
Two construction variables are in the same family if they are in the same group , are of the same kind (root bit or selector) and have the same depth .
Within a group, for each the selectors form the family at depth , and the root bits and the root selectors form two separate families at depth . Each restriction round treats each family independently.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_CVar
namespace AvgPHETH.Supplement
/-- Two construction variables are in the same **family**: the same group `(k, n = |x|)`, the same
kind and the same depth. Within a group, the root bits `B^k_x` and the root selectors `S^k_x` form two
separate families at depth `0`, and for `1 ≤ j < k` the selectors `S^k_{x,y₁,…,y_j}` form the family
at depth `j` (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)). -/
def CVar.SameFamily (v w : CVar) : Prop :=
v.k = w.k ∧ v.x.length = w.x.length ∧ v.isBit = w.isBit ∧ v.path.length = w.path.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)