Critical assignments of a formula
DefinitionAvgPHETH_Supplement_Formula_IsCriticalcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
The neutral value of an AND gate is and that of an OR gate is . An assignment to the variables of a formula is critical for if, under , every gate of has at most one child that does not evaluate to the gate's neutral value: at most one child of each AND gate evaluates to , and at most one child of each OR gate evaluates to .
Theorem 7.1 is a lower bound against circuits that only have to agree with the hard formula on its critical assignments.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_Formula
import Definitions.Def_AvgPHETH_Supplement_Formula_eval
namespace AvgPHETH.Supplement
/-- An assignment `α` is **critical** for the formula `F` if every gate of `F` has at most one child
that does not evaluate to the gate's neutral value (`1` for AND, `0` for OR)
(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)).
**Formalization Note** The neutral value of `gate a m ch` is `a` itself (`true` for AND). -/
def Formula.IsCritical {V : Type} (α : V → Bool) : Formula V → Prop
| .leaf _ => True
| .gate a _ ch => {i | (ch i).eval α ≠ a}.Subsingleton ∧ ∀ i, (ch i).IsCritical α
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 'Critical assignments', p.16 (PDF 18)