Many collective labeling tasks require inference on graphical models where the clique potentials depend only on the number of nodes that get a particular label. We design efficient inference algorithms for various families of such potentials. Our algorithms are exact for arbitrary cardinality-based clique potentials on binary labels and for max-like and majority-like clique potentials on multiple labels. Moving towards more complex potentials, we show that inference becomes NP-hard even on cliques with homogeneous Potts potentials. We present a 13/15-approximation algorithm with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 0.5. We perform empirical comparisons on real and synthetic data, and show that our proposed methods are an order of magnitude faster than the well-known Tree-based re-parameterization (TRW) and graph-cut algorithms.

A heuristic for finding common subexpressions of given Boolean functions based on Shannon-type factoring is proposed. This heuristic limits the search space considerably by applying a top-down approach in which synthesis of a Boolean network flows from the primary outputs to the primary inputs. The common subexpressions and their complements in N variables are extracted before common subexpressions and their complements in (N-1) variables. This decomposition of the network depends on a permutation of Boolean variables and has a polynomial complexity for restricted extraction of complements. A multilevel logic optimization system, MULTI, has been implemented using this heuristic. Good results on several benchmark circuits show its effectiveness.>