Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression

摘要

A Boolean function f:{0,1}n→{0,1} is weighted symmetric if there exist a function g:Z→{0,1} and integers w0,w1,…,wn such that f(x1,…,xn)=g(w0+∑i=1nwixi) 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 2n 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(nt)⋅2n−n1/O(t) for instances with n variables and O(nt) 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.