ECCC-Report TR16-100https://eccc.weizmann.ac.il/report/2016/100Comments and Revisions published for TR16-100en-usMon, 27 Jun 2016 14:00:28 +0300
Paper TR16-100
| A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates |
Suguru Tamaki
https://eccc.weizmann.ac.il/report/2016/100We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time super-polynomially faster than $2^n$ if $m=O(n^2/\log^b n)$ for some constant $b>0$. Previously, such algorithms were only known for bounded depth circuits with linear threshold gates and a slightly super-linear number of wires [Impagliazzo-Paturi-Schneider, FOCS 2013 and Chen-Santhanam-Srinivasan, CCC 2016].
We also show that depth 2 circuits with $O(n^2/\log^b n)$ symmetric and linear threshold gates in total cannot compute an explicit function computable by a deterministic $2^{O(n)}$-time Turing machine with an NP oracle. Previously, even slightly super-linear lower bounds on the number of gates were not known until recently Kane and Williams [STOC 2016] showed that depth 2 linear threshold circuits with $o(n^{3/2}/\log^3 n)$ gates cannot compute an explicit function computable in linear time.Mon, 27 Jun 2016 14:00:28 +0300https://eccc.weizmann.ac.il/report/2016/100