Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC

摘要

We answer the question: What are the Boolean functions that can be computed with a constant number of bit-exchange in a two-processor environment no matter how the input bits are distributed among the processors?The characterization uses “programs over a monoid M,” a construction introduced by D. Barrington. We prove that if the symmetric communication complexity of a Boolean function f is at most c (i.e., the communication complexity is at most c for all possible partitions of the input into two parts) then there is a commutative monoid M of size at most exp(exp(exp(exp(exp c)))) such that a program over the monoid M can be built that computes f. We also give size and depth upper bounds for synchronous circuits that compute functions with bounded symmetric communication complexity, as well as width upper bounds for read-only once branching programs that compute these functions.