Communication complexity and combinatorial lattice theory

Laészloé Lovǎsz, Michael Saks

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


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
Issue number2
StatePublished - 1993

All Science Journal Classification (ASJC) codes

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


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

Cite this