Communication complexity and combinatorial lattice theory

Laészloé Lovǎsz, Michael Saks

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

In a recent paper, Hajnal, Maass, and Turaén analyzed the communication complexity of graph connectivity. Building on this work, we develop a general framework for the study of a broad class of communication problems which has several interesting special cases including the graph connectivity problem. The approach is based on the combinatorial theory of alignments and lattices.

Original languageEnglish (US)
Pages (from-to)322-349
Number of pages28
JournalJournal of Computer and System Sciences
Volume47
Issue number2
DOIs
StatePublished - 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Communication complexity and combinatorial lattice theory'. Together they form a unique fingerprint.

Cite this