Total assignments consistent with a partial assignment
DefinitionAvgPHETH_Supplement_Completionsaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a partial assignment to the construction variables, these are the total assignments that agree with on every assigned variable and give every variable a value of its alphabet.
They are the assignments to the unset construction variables over which the function of step 2(a) is evaluated.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_CVar_IsValid
import Definitions.Def_AvgPHETH_Supplement_CVar_valLen
namespace AvgPHETH.Supplement
/-- The total assignments to the construction variables that extend the partial assignment `ρ`: every
assigned variable keeps its value and every variable gets a value of its alphabet. These are the
assignments to "the unset construction variables" over which the function `f_q` of step 2(a) ranges
(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.41 (PDF 43)). -/
def Completions (ε : ℕ → ℝ) (ρ : CVar → Option (List Bool)) : Set (CVar → List Bool) :=
{τ | ∀ v : CVar, (∀ b, ρ v = some b → τ v = b) ∧ (v.IsValid ε → (τ v).length = v.valLen ε)}
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, steps 2(a) and 3(b), p.41 (PDF 43)