The wire size of a De Morgan circuit
DefinitionHypercliqueAC0_FixedDepth_Supplement_Wirescircuit-complexitycomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a De Morgan circuit: a directed acyclic graph whose inputs are literals and constants and whose gates compute AND or OR of arbitrary fan-in. Its wire size is the number of edges of the underlying graph, that is, the total fan-in
Every input of a gate, whether a literal, a constant or another gate, contributes one wire. The gates themselves are not counted, so differs from the size "gates plus wires". The wire size is the complexity measure of the depth-three lower bound for .
Formalization Note The circuit is the published MantriCVQ.ACCircuit, a list of gates each with a list of inputs; is the sum of the lengths of these input lists. A repeated entry in an input list counts as a separate wire.
Definition code
import Mathlib
import Definitions.Def_MantriCVQ_ACCircuit
namespace HypercliqueAC0.FixedDepth.Supplement
/-- The wire size `W(C)` (§3.2, p. 10, PDF 12): the number of edges of the circuit's underlying
graph, i.e. the total fan-in of its gates. Every entry of a gate's input list (a literal, a
constant or an earlier gate) is one wire. Unlike `MantriCVQ.ACCircuit.size`, the gates themselves
are not counted. -/
def wires {V : Type} (C : MantriCVQ.ACCircuit V) : ℕ :=
(C.gates.map (fun g => g.inputs.length)).sum
end HypercliqueAC0.FixedDepth.Supplement
Source
Nikolai Chukhin, Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors, STOC 2027 submission #830 (October 2026), source.pdf SHA-256 bd73fd887fe562527226e0ea2da24a55552a73cf89c2e90406a28965424a12de, p.10 (PDF p.12), §3.2 Boolean Circuits (wire size W(C))