__
TR15-136 | 28th July 2015 15:20
__

#### A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom

**Abstract:**
In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of

depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.

As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in time

$\poly(n^t) \cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables and $O(n^t)$ clauses.