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

DOI10.4230/LIPICS.CCC.2016.1MaRDI QIDQ5368735zbMATH OpenOpenAlexFDO

Authors Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

Publication date 10 October 2017

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

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)

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.

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

Cited in

(14)

• Satisfiability and derandomization for small polynomial threshold circuits
• 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\)
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• 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

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)