Communication complexity and combinatorial lattice theory
type: Item
instance of: scholarly article
title: Communication complexity and combinatorial lattice theory
zbMATH Open document ID: 0791.68083
DOI: 10.1016/0022-0000(93)90035-U
published in: Journal of Computer and System Sciences
publication date: 1993-12-20T00:00:00Z
review text: Using results of Turán, Maass and Hajnal on the communication complexity of graph connectivity as a point of entry, the authors develop a general model for mathematical investigations of broad classes of communication problems, computational problems and processing problems. The applications are nearly obvious: relations to time-area tradeoffs for VHSI circuits and the crypto-complexity of secrecy systems. The authors give a succinct review of the area of communications, prove several formal equivalences between various communication models and give explicit protocols for disjointness problems for two basic classes of convex geometries. Three open problems are discussed; e.g., is the deterministic complexity of any relation bounded by a polylogarithmic function of the rank of its characteristic matrix over the reals? The paper includes 34 basic references and has many applications to entropic limitations of UHSI computation and communication.
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 68W35
zbMATH DE Number: 472879
zbMATH Keywords: lattice theory
zbMATH Keywords: distributed computing
zbMATH Keywords: matroid invariants
zbMATH Keywords: convexity
zbMATH Keywords: VLSI
zbMATH Keywords: communication complexity
zbMATH Keywords: graph connectivity
author: Michael Saks
author: László Lovász
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
cites work: Lower Bounds on Information Transfer in Distributed Computations
cites work: A counterexample to the rank-coloring conjecture
cites work: A higher invariant for matroids
cites work: Whitney Number Inequalities for Geometric Lattices
cites work: Lower bounds on communication complexity
cites work: The theory of convex geometries
cites work: Q5595624
cites work: Solving Undirected Graph Problems on VLSI
cites work: Q3951161
cites work: The VLSI Complexity of Selected Graph Problems
cites work: Information Transfer under Different Sets of Protocols
cites work: Q3346344
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Determinants on Semilattices
cites work: A Bound for the Chromatic Number of a Graph
cites work: Communication complexity
cites work: Probabilistic communication complexity
cites work: On recognizing graph properties from adjacency matrices
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Q4111952
Recommended article: Communication complexity in lattices
Recommended article: Composition Theorems in Communication Complexity
Recommended article: Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
Recommended article: Kolmogorov complexity and combinatorial methods in communication complexity
Recommended article: Communication Complexity
Recommended article: On a communication complexity problem in combinatorial number theory
Recommended article: Q4219022
Recommended article: Algebraic techniques in communication complexity
Recommended article: Q5203681
description: scientific article; zbMATH DE number 472879