Average-case lower bounds and satisfiability algorithms for small threshold circuits

DOI10.4230/LIPICS.CCC.2016.1zbMATH Open1380.68191arXiv1806.06290OpenAlexW2460503887MaRDI QIDQ5368735FDOQ5368735

Authors: Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan 

Publication date: 10 October 2017

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 a constant $varepsilo{n}_d>0$ such that the Parity function on $n$ bits has correlation at most $n^{-varepsilo{n}_d}$ with depth-$d$ threshold circuits which have at most $n^{1+varepsilo{n}_d}$ wires, and the Generalized Andreev function on $n$ bits has correlation at most $exp(-n^{varepsilo{n}_d})$ with depth-$d$ threshold circuits which have at most $n^{1+varepsilo{n}_d}$ wires. Previously, only worst-case lower bounds in this setting were known (Impagliazzo, Paturi, and Saks (SICOMP 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 on $n$ bits cannot be computed by polynomial-size $extsf{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 $extsf{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 of any depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

Full work available at URL: https://arxiv.org/abs/1806.06290

Recommendations

• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Size--Depth Tradeoffs for Threshold Circuits
• Approximating threshold circuits by rational functions
• Exponential lower bound for bounded depth circuits with few threshold gates

zbMATH Keywords

satisfiability algorithmthreshold circuitcircuit lower bound

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (14)

• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• An average-case lower bound against \(\mathsf{ACC}^0\)
• Title not available (Why is that?)
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• An average-case depth hierarchy theorem for Boolean circuits
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• Quantified Derandomization: How to Find Water in the Ocean
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Satisfiability and derandomization for small polynomial threshold circuits

This page was built for publication: Average-case lower bounds and satisfiability algorithms for small threshold circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368735)