Some Order Dimension Bounds for Communication Complexity Problems
Faigle, Ulrich and Kern, Walter
(1991)
Some Order Dimension Bounds for Communication Complexity Problems.
Published in:
Acta Informatica Vol. 28 (6).
pp. 593601.
Abstract
We associate with a general (0,1)matrix M an ordered set P(M) and derive lower and upper bounds for the deterministic communication complexity of M in terms of the order dimension of P(M). We furthermore consider the special class of communication matrices M obtained as cliques vs. stable sets incidence matrices of comparability graphs G. We bound their complexity by O((log d)cdot (log n)), where n is the number of nodes of G and d is the order dimension of an orientation of G. In this special case, our bound is shown to improve other wellknown bounds obtained for the general cliques vs. stable set problem.
Item Type:  Article 

Citations:  0 (Google Scholar)  0 (Web of Science) 
Uncontrolled Keywords:  communication complexity ordered sets 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr90086 

Depositing User:  Prof. Dr. Ulrich Faigle 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  24 Oct 2011 08:59 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/86 