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. 593-601.


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 well-known bounds obtained for the general cliques vs. stable set problem.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr90-086
Depositing User: Prof. Dr. Ulrich Faigle
Date Deposited: 02 Apr 2001 00:00
Last Modified: 24 Oct 2011 08:59