摘要：We show average-case lower bounds for explicit Boolean functions against
bounded-depth threshold circuits with a superlinear number of wires. We show that for
each integer d > 1, there is a constant εd > 0 such that the Parity function on n bits has
correlation at most n
−εd with depth-d threshold circuits which have at most n
1+εd wires, and
the Generalized Andreev function on n bits has correlation at most exp(−n
εd ) with depth-d
threshold circuits which have at most n
1+εd wires. Previously, only worst-case lower bounds
in this setting were known (Impagliazzo, Paturi, and Saks (SICOMP 1997)).
关键词：complexity theory; circuit complexity; correlation bounds; threshold functions;;
random restrictions; learning; SAT
