Satisfiability and Compression Algorithms for Bounded-Depth Circuits with Symmetric Gates

We consider the circuit satisfiability problem and the circuit compression problem for bounded-depth circuits with symmetric gates (AC^0+SYMs). In the former problem, the task is, given an n-variable polynomial-size AC^0+SYMs circuit C, to decide whether there exists a truth assignment to the input variables such that C evaluates true. For this problem, we give an algorithm that runs in time super-polynomially faster than 2^n when the number of symmetric gates is bounded. In the latter problem, the task is, given the truth-table of an n-variable polynomial-size AC^0+SYMs circuit C, to construct a Boolean circuit that computes the same function as C and has size sufficiently smaller than 2^n/n. For this problem, we show an algorithm that runs in time 2^{O(n)} when the number of symmetric gates is bounded.

Joint work with Takayuki Sakai, Kazuhisa Seto, Junichi Teruyama.