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

作者:

Highlights:

摘要

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.

论文关键词:

论文评审过程:Received 14 September 1990, Revised 21 February 1992, Available online 2 December 2003.

论文官网地址:https://doi.org/10.1016/0022-0000(93)90039-Y