Chen, Ruiwen ;
Santhanam, Rahul ;
Srinivasan, Srikanth
AverageCase Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Abstract
We show averagecase lower bounds for explicit Boolean functions against boundeddepth 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 depthd threshold circuits which have at most n^{1+epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{Omega(1)}} with depthd threshold circuits which have at most n^{1+epsilon_d} wires. Previously, only worstcase lower bounds in this setting were known [Impagliazzo/Paturi/Saks, SIAM J. Comp., 1997].
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 polynomialsize AC^0 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 subexponentialtime learning algorithms for AC^0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depthd threshold circuit computing Parity on average, and show averagecase lower bounds for threshold formulas ofany depth.
Our techniques include adaptive random restrictions, anticoncentration and the structural theory of linear threshold functions, and boundedread Chernoff bounds.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2016:5844,
author = {Ruiwen Chen and Rahul Santhanam and Srikanth Srinivasan},
title = {{AverageCase Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {1:11:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5844},
URN = {urn:nbn:de:0030drops58447},
doi = {10.4230/LIPIcs.CCC.2016.1},
annote = {Keywords: threshold circuit, satisfiability algorithm, circuit lower bound}
}
2016
Keywords: 

threshold circuit, satisfiability algorithm, circuit lower bound 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 