Exponentially small correlation with quadratic forms #
Fan-in-two circuits over any basis with at most c n gates of positive arity, for any
c < c* = 1 + 1/(2A) ≈ 2.78125, have correlation 2^{-Ω(n)} with an explicit family of
bilinear forms xᵀ R y over GF(2). Here A = 2p ≈ 0.2807 is the Gaussian layout coefficient
of the frontier method (Frontier.layoutBound_gaussian). The circuit model, the gate count
(Cslib.Circuits.Circuit.innerSize), and the agreement measure are those of the frontier
method's average-case theorem Frontier.averageCase_abs, so the bounds are directly
comparable. The best previously published average-case bounds for the full binary basis are
2.5 n (Chen–Kabanets, COCOON 2015, for an explicit affine extractor) and 2.6 n
(Golovnev–Kulikov–Smal–Tamaki, MFCS 2016, for non-explicit quadratic extractors).
The argument #
For a quadratic form f and a cut X of the coordinates, Lindsey's lemma bounds the signed sum
of (-1)^f over every rectangle R for X by √(|R| 2^{n - ρ(X)}), where the cut rank
ρ(X) is the rank of the block of the polar matrix with rows X and columns Xᶜ. Partition
the inputs into K rectangle classes for one cut on which the circuit is constant;
Cauchy–Schwarz over the classes gives correlation² ≤ K · 2^{-ρ(X)}. Two partitions apply:
- if the circuit leaves the inputs
Dunread, its two output classes are rectangles forD(correlation_sq_le_of_unread); - along a layout of the compiled constraint network of width
w, the output and the values on the frontier when exactly⌊n/2⌋inputs have been read give2 · 2^wrectangle classes (correlation_sq_le_of_layout).
If every set of ⌊n/2⌋ coordinates has cut rank at least ⌊n/2⌋ - τ n, balancing the two at
θ n unread inputs, with θ = (1/2 - A (c - 1))/(1 + A), gives the rate
(c* - c)/(2L) - τ/2 with L = 1 + 1/A (eventually_correlation_le), and
(c* - c)/(2L) for a sublinear deficiency (eventually_correlation_le_of_isLittleO,
eventually_correlation_le_gaussian).
The explicit family #
A matrix is submatrix-robust with deficiency t when every square block with k rows has rank
at least k - t. Counting spanning sets of columns shows that for t = 2 ⌊√m⌋ + 1 such an
m × m matrix exists (exists_submatrixRobust). The family hardForm n = xᵀ R y uses a fixed
such matrix robustMatrix (⌊n/2⌋), chosen once and for all by Classical.choose; its
bisection cut rank is at least ⌊n/2⌋ - O(√n) (half_le_cutRank_hardMatrix). Taking instead
the lexicographically first robust matrix makes the family computable in E^NP: whether some
robust matrix extends a given prefix is one NP query of length 2^{O(n)} (guess the matrix
and check its fewer than 4^{n/2} pairs of row and column sets), so the matrix is found bit by
bit in time 2^{O(n)}. This uniformity is a remark about the construction and is not
formalized.
Main results #
correlation_sq_mul_two_pow_cutRank_le: correlation through rectangle classes.correlation_sq_le_of_unread,correlation_sq_le_of_layout: the finite bounds.eventually_correlation_le,eventually_correlation_le_of_isLittleO,eventually_correlation_le_gaussian: correlation2^{-γ n}for every family of quadratic forms whose bisection cut rank is⌊n/2⌋ - o(n).exists_submatrixRobust: robust matrices exist, by exact counting.eventually_correlation_hardForm_le: the headline bound for the explicit family.exists_eventually_correlation_hardForm_le: below2.77 ngates, the correlation with the explicit family is2^{-γ n}for a fixedγ > 0.
Rectangle classes #
Correlation through rectangle classes. Let g be constant on the classes of msg, and
let every class be a rectangle for one cut X of the coordinates. Then the correlation of g
with the quadratic form of Q satisfies correlation² · 2^{cutRank Q X} ≤ |M|, where M is
the type of messages. This is Lindsey's lemma on each class and Cauchy–Schwarz over the
classes.
Finite bounds for circuits #
Unread inputs. If every set of ⌊n/2⌋ coordinates has cut rank at least
⌊n/2⌋ - e, a circuit that leaves at least k ≤ ⌊n/2⌋ inputs unread has
correlation² ≤ 2^{1 + e - k} with the quadratic form.
The frontier bound. If every set of ⌊n/2⌋ coordinates has cut rank at least
⌊n/2⌋ - e, a circuit that reads at least ⌊n/2⌋ inputs, whose compiled constraint network
has a layout with every frontier of at most w edges, has
correlation² ≤ 2^{1 + w + e - ⌊n/2⌋} with the quadratic form.
Asymptotic bounds for families of quadratic forms #
Exponentially small correlation. Under the layout hypothesis with coefficient A,
let every set of ⌊n/2⌋ coordinates have cut rank at least ⌊n/2⌋ - τ n for all large n.
Then for every c ≥ 1/2 and every γ < (c* - c)/(2L) - τ/2, where c* = 1 + 1/(2A) and
L = 1 + 1/A, for all large n every fan-in-two circuit over any basis with at most c n gates
of positive arity has correlation at most 2^{-γ n} with the quadratic form.
Exponentially small correlation, sublinear deficiency. Under the layout hypothesis with
coefficient A, if every set of ⌊n/2⌋ coordinates has cut rank at least ⌊n/2⌋ - o(n),
then for every c ≥ 1/2 and every γ < (c* - c)/(2L), for all large n every fan-in-two
circuit with at most c n gates of positive arity has correlation at most 2^{-γ n} with the
quadratic form.
The Gaussian threshold and rate constants in closed form.
Exponentially small correlation below 2.78 n gates. If every set of ⌊n/2⌋
coordinates has cut rank at least ⌊n/2⌋ - o(n), then for every c ≥ 1/2 and every
γ < (c* - c)/(2L), with c* = 1 + π/(6 arccos((1 + 2√2)/4)) ≈ 2.78125 and
L = 1 + π/(3 arccos((1 + 2√2)/4)) ≈ 4.5625, for all large n every fan-in-two circuit over
any basis with at most c n gates of positive arity has correlation at most 2^{-γ n} with the
quadratic form.
Robust matrices and the explicit family #
Submatrix-robust matrices exist. For every m some m × m matrix over GF(2) has
every square block with k rows of rank at least k - (2 ⌊√m⌋ + 1). The proof counts, for each
block, the matrices whose columns there are spanned by few of them.
A fixed submatrix-robust m × m matrix, chosen once and for all.
Equations
Instances For
The explicit hard family: on inputs of length n, the bilinear form xᵀ R y of the
fixed robust matrix R = robustMatrix ⌊n/2⌋.
Equations
Instances For
Headline: exponentially small correlation with an explicit family below 2.78 n gates.
For every c ≥ 1/2 and every γ < (c* - c)/(2L), with
c* = 1 + π/(6 arccos((1 + 2√2)/4)) ≈ 2.78125 and L = 1 + π/(3 arccos((1 + 2√2)/4)) ≈ 4.5625,
for all large n every fan-in-two circuit over any basis with at most c n gates of positive
arity has correlation at most 2^{-γ n} with hardForm n.
Below 2.77 n gates. Some fixed γ > 0 bounds, for all large n, the correlation of
every fan-in-two circuit over any basis with at most 2.77 n gates of positive arity with
hardForm n by 2^{-γ n}.