On the communication complexity of t-intersection problems in generalized Boolean algebras

U. Faigle, Walter Kern, B.A. Spieker, Boris Spieker

Research output: Contribution to journalArticleAcademicpeer-review

33 Downloads (Pure)

Abstract

We consider the following game: Two players independently choose a chain in a partially ordered set. How many bits of information have to be communicated until at least one of the players knows whether the chains have exactlyt elements in common? This model generalizes thet-intersection problem for subsets of a finite set. We establish the deterministic communication complexity in general. For the special cases of generalized Boolean algebras, we present improved nondeterministic and probabilistic protocols that are of optimal order of complexity for classes with fixed widthq.
Original languageUndefined
Pages (from-to)239-254
Number of pages16
JournalMathematical methods of operations research
Volume43
Issue number2
DOIs
Publication statusPublished - 1996

Keywords

  • IR-85178
  • METIS-140767

Cite this