Some order dimension bounds for communication complexity problems

U. Faigle, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

64 Downloads (Pure)

Abstract

We associate with a general (0, 1)-matrixM an ordered setP(M) and derive lower and upper bounds for the deterministic communication complexity ofM in terms of the order dimension ofP(M). We furthermore consider the special class of communication matricesM obtained as cliques vs. stable sets incidence matrices of comparability graphsG. We bound their complexity byO((logd)·(logn)), wheren is the number of nodes ofG andd is the order dimension of an orientation ofG. In this special case, our bound is shown to improve other well-known bounds obtained for the general cliques vs. stable set problem.
Original languageUndefined
Pages (from-to)593-601
Number of pages9
JournalActa informatica
Volume28
Issue number6
DOIs
Publication statusPublished - 1991

Keywords

  • METIS-140502
  • IR-98374

Cite this