Depth-two threshold circuits for parity -- definitions

On N inputs, internal gate j < N is the unweighted threshold gate "at least j + 1 of the inputs are true". If w inputs are true, gate j is true exactly when j < w. The output gate reads every internal gate, negating the odd-indexed ones through the free per-input flags, and fires when at least N / 2 + 1 of these signed inputs are true. Exactly N / 2 + w % 2 of them are true, so the output is the parity of w.

The circuit has N internal gates and one output gate, so its size is N + 1, and its depth is two. The family answers false on the empty input, the parity of the empty string.

def Complexity.Circuit.thresholdParityLayerGate (N : ℕ) (j : Fin N) : Gate Basis.threshold (N + N)

Internal gate j of the parity circuit on N inputs: true exactly when at least j + 1 of the N primary inputs are true.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.Circuit.thresholdParityOutputGate (N : ℕ) : Gate Basis.threshold (N + N)

Output gate of the parity circuit on N inputs: it reads internal gate j for every j < N, negated exactly when j is odd, and requires at least N / 2 + 1 true signed inputs.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.Circuit.thresholdParity (N : ℕ) [NeZero N] : Circuit Basis.threshold N 1 N

The depth-two threshold circuit for N-input parity, with N internal gates.

Equations

• Complexity.Circuit.thresholdParity N = { gates := Complexity.Circuit.thresholdParityLayerGate N, outputs := fun (x : Fin 1) => Complexity.Circuit.thresholdParityOutputGate N, acyclic := ⋯ }

def Complexity.CircuitFamily.thresholdParity : CircuitFamily Basis.threshold

The threshold-circuit family for parity: Circuit.thresholdParity n at every positive length n, and false on the empty input.

Equations

• Complexity.CircuitFamily.thresholdParity = { emptyOutput := false, circuits := fun (n : ℕ) (x : NeZero n) => ⟨n, Complexity.Circuit.thresholdParity n⟩ }