Output of an alternating circuit
DefinitionAvgPHETH_Supplement_AltCircuit_evalcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
The output of an alternating circuit under an assignment is the value of its single gate in layer .
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_AltCircuit_layerVal
namespace AvgPHETH.Supplement
/-- The output `C(α)` of an alternating circuit: the value of its single gate in layer `depth`
(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 AltCircuit.eval {V : Type} (C : AltCircuit V) (α : V → Bool) : Bool :=
C.layerVal α C.depth ⟨0, by rw [C.single_output]; exact Nat.one_pos⟩
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)