Search

A Boolean function f : { 0 , 1 } n → { 0 , 1 } is weighted symmetric if there exist a function g : Z → { 0 , 1 } and integers w 0 , w 1 , ... , w n such that f (x 1 , ... , x n) = g (w 0 + ∑ i = 1 n w i x i) holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run in time super-polynomially faster than 2 n even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in time poly (n t) ⋅ 2 n − n 1 / O (t) for instances with n variables and O (n t) clauses. Through the analysis of our algorithms, we show average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits. [ABSTRACT FROM AUTHOR]