A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates
Suguru Tamaki · 2025
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 \textrm{poly}(\log n)}\right) ^a\right) }$$ 2 n - Ω n m · poly ( log n ) a for some constant $$a>0$$ a > 0 . Our algorithm runs in time super-polynomially faster than $$2^n$$ 2 n if $$m=O(n^2/\log ^b n)$$ m = O ( n 2 / log b n ) for some constant $$b>0$$ 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)$$ 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)}$$ 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)$$ o ( n 3 / 2 / log 3 n ) gates cannot compute an explicit function computable in linear time.