Internal fan-in bound
DefinitionAvgPHETH_Supplement_Formula_FanInLecircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
A formula has all internal fan-ins at most if every gate has at most children.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_Formula
namespace AvgPHETH.Supplement
/-- `F.FanInLe B`: every internal fan-in (number of children of a gate) of `F` is at most `B`
(Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), Theorem 7.1, p.30 (PDF 32)). -/
def Formula.FanInLe {V : Type} : Formula V → ℕ → Prop
| .leaf _, _ => True
| .gate _ m ch, B => m ≤ B ∧ ∀ i, (ch i).FanInLe B
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…), Theorem 7.1, p.30 (PDF 32)