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

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)405-423
Number of pages19
JournalJournal of Computer and System Sciences
Volume47
Issue number3
DOIs
StatePublished - Jan 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC'. Together they form a unique fingerprint.

Cite this