The average-case (4 - ε) n bound #
A circuit with at most (4 - ε) n gates agrees with a (K, ν)-balanced
function on at most (1/2 + 3ν) 2ⁿ + 2^{(1 - ε/24) n} inputs, for K
polynomial and n large, under the graph-ordering hypothesis.
This does not follow from the worst-case cut-counting lemma: an input whose
past set is still small at a vertex lies in a thin rectangle, on which a
balanced function is unconstrained. Instead the proof uses the direction of
the wiring graph. At a cut, the forward-crossing bits are determined by the
inputs read so far and the backward-crossing bits (trace_eq_of_agree_backward),
and symmetrically for the future. This caps the number of cut assignments a
fixed past or future can see, so the thin mass at a prefix L is at most
(K - 1)(2^{n - a(L)} + 2^{n - c(L)}) with
a(L) = |past L| - |forward cut| and c(L) = n - |past L| - |backward cut|.
Along the vertex order a grows from 0 to the number of inputs read in
steps of at most four, and a + c = n - |cut|, so a prefix with both a and
c linear exists whenever the cutwidth is below (1 - Ω(ε)) n.
Circuits reading few inputs are handled separately: on every subcube fixing the read inputs the circuit is constant, and a balanced function is close to one half on a rectangle refining that subcube.
The attribution of the underlying compiler is as in FourN.
The wiring network has unique, direction-determined assignments #
Balanced functions on subcubes #
The whole cube split at u coordinates is a rectangle with sides 2^u
and 2^(n-u), so a balanced function accepts within ν of half of all inputs
once both exceed K.
Few inputs read. If g depends only on R and at least 2 ⌈log₂ K⌉
coordinates lie outside R, then g agrees with a (K, ν)-balanced f on
at most (1/2 + ν) 2ⁿ inputs: on each subcube fixing R, g is constant,
and refining the subcube by ⌈log₂ K⌉ free coordinates gives a rectangle on
which f is balanced.
A good prefix of the vertex order #
Processing one vertex adds to the past at most one variable when no two variables are read at the same vertex.
A good prefix. For quantities P and F on the prefixes of a finite
linear order with P ∅ = 0, t + F univ ≤ P univ, P growing by at most one
and F dropping by at most three per vertex, some prefix L has
t ≤ P L - F L < t + 4.
A vertex of the wiring graph reads at most one variable.
Assembly #
The numeric core of the average case. At a good prefix, twice the
thin-rectangle mass of the one-sided count is at most 2 ^ ((1 - ε/24) n),
once n satisfies an explicit logarithmic condition.
The fixed-n average-case bound. With the graph-ordering hypothesis
for slack η ≤ ε/36, a circuit with at most (4 - ε) n binary gates agrees
with a (K, ν)-balanced function, K ≤ n ^ c, on at most
(1/2 + 3ν) 2ⁿ + 2 ^ ((1 - ε/24) n) inputs, once n satisfies an explicit
logarithmic condition.
Theorem (average case). Assume the graph-ordering lemma for every
slack η > 0 and a family f n that is (K n, ν)-balanced with K n ≤ n ^ c
for all large n. Then for every ε > 0 and all sufficiently large n,
every binary circuit with at most (4 - ε) n gates agrees with f n on at
most (1/2 + 3ν) 2ⁿ + 2 ^ ((1 - ε/24) n) inputs.
The average case from the pathwidth hypothesis.