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

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

0.00 Avg rating0 Votes
Article ID: iaor19972444
Country: Germany
Volume: 43
Issue: 2
Start Page Number: 239
End Page Number: 254
Publication Date: Mar 1996
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Keywords: boolean programming
Abstract:

The authors 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 exactly t elements in common? This model generalizes the t-intersection problem for subsets of a finite set. The authors establish the deterministic communication complexity in general. For the special cases of generalized Boolean algebra, they present improved nondeterministic and probabilistic protocols that are of optimal order of complexity for classes with fixed width q.

Reviews

Required fields are marked *. Your email address will not be published.