License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.1
URN: urn:nbn:de:0030-drops-58447
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5844/
Chen, Ruiwen ;
Santhanam, Rahul ;
Srinivasan, Srikanth
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Abstract
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 most n^{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 [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 polynomial-size 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 subexponential-time 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 depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas ofany depth.
Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2016:5844,
author = {Ruiwen Chen and Rahul Santhanam and Srikanth Srinivasan},
title = {{Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {1:1--1:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-008-8},
ISSN = {1868-8969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5844},
URN = {urn:nbn:de:0030-drops-58447},
doi = {10.4230/LIPIcs.CCC.2016.1},
annote = {Keywords: threshold circuit, satisfiability algorithm, circuit lower bound}
}
|
Keywords: |
|
threshold circuit, satisfiability algorithm, circuit lower bound |
|
Collection: |
|
31st Conference on Computational Complexity (CCC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.05.2016 |
