TY - UNPB

T1 - Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

AU - Chen, Ruiwen

AU - Santhanam, Rahul

AU - Srinivasan, Srikanth

PY - 2015

Y1 - 2015

N2 - 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 \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at mostn^{1+\epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{\Omega(1)}} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [22].We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential- time learning algorithms for AC0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth.Our techniques include adaptive random restrictions, anti-concentration and the structural theory of threshold functions, and bounded-read Chernoff bounds.

AB - 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 \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at mostn^{1+\epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{\Omega(1)}} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [22].We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential- time learning algorithms for AC0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth.Our techniques include adaptive random restrictions, anti-concentration and the structural theory of threshold functions, and bounded-read Chernoff bounds.

M3 - Working paper

VL - 22

SP - 191

BT - Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

ER -