Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR16-100 | 27th June 2016 03:15

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

TR16-100
Authors: Suguru Tamaki
Publication: 27th June 2016 14:00
Keywords:

Abstract:

We 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.

ISSN 1433-8092 | Imprint