Communication complexity and combinatorial lattice theory

Laészloé Lovǎsz; Michael Saks

doi:10.1016/0022-0000(93)90035-U

Communication complexity and combinatorial lattice theory

Laészloé Lovǎsz, Michael Saks

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

35 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 language	English (US)
Pages (from-to)	322-349
Number of pages	28
Journal	Journal of Computer and System Sciences
Volume	47
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(93)90035-U
State	Published - 1993

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/0022-0000(93)90035-U

Cite this

@article{ec23a7f250eb4c57b383d35b029e1a62,

title = "Communication complexity and combinatorial lattice theory",

abstract = "In a recent paper, Hajnal, Maass, and Tura{\'e}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.",

author = "La{\'e}szlo{\'e} Lovǎsz and Michael Saks",

note = "Funding Information: * Supported in part by NSF Grants DMS87 03541, CCR89-11388 and Air Force Office of Scientific Research Grant AFOSR-0271.",

year = "1993",

doi = "10.1016/0022-0000(93)90035-U",

language = "English (US)",

volume = "47",

pages = "322--349",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Communication complexity and combinatorial lattice theory

AU - Lovǎsz, Laészloé

AU - Saks, Michael

N1 - Funding Information: * Supported in part by NSF Grants DMS87 03541, CCR89-11388 and Air Force Office of Scientific Research Grant AFOSR-0271.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=25544437705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25544437705&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(93)90035-U

DO - 10.1016/0022-0000(93)90035-U

M3 - Article

AN - SCOPUS:25544437705

SN - 0022-0000

VL - 47

SP - 322

EP - 349

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Communication complexity and combinatorial lattice theory

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this