2026-07-23T03:28:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5844 2024-03-06T10:37:08Z ddc:004 open_access

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits Chen, Ruiwen Santhanam, Rahul Srinivasan, Srikanth threshold circuit satisfiability algorithm circuit lower bound 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ruiwen Chen and Rahul Santhanam and Srikanth Srinivasan 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.1 urn:nbn:de:0030-drops-58447 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.1 eng https://creativecommons.org/licenses/by/3.0/legalcode