Value of a formula
DefinitionAvgPHETH_Supplement_Formula_evalcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under an assignment , a leaf takes the value of its label, an AND gate takes value iff all its children do, and an OR gate takes value iff some child does.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_Formula
import Definitions.Def_AvgPHETH_Supplement_Lit_eval
namespace AvgPHETH.Supplement
/-- The value of a formula under an assignment `α` (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §4.3, p.16 (PDF 18)). -/
def Formula.eval {V : Type} (α : V → Bool) : Formula V → Bool
| .leaf l => l.eval α
| .gate true _ ch => decide (∀ i, (ch i).eval α = true)
| .gate false _ ch => decide (∃ i, (ch i).eval α = 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…), §4.3, p.16 (PDF 18)