Lattices, Möbius Functions and Communication Complexity

A general framework for the study of a broad class of communication problems is developed. It is based on a recent analysis of the communication complexity of graph connectivity. The approach makes use of combinatorial lattice theory. >

Authors

• László Lovász 0001
• Michael E. Saks

Keywords

• Lattices
• Complexity theory
• Protocols
• Geometry
• Polynomials
• Complex Communication
• Lower Bound
• Upper Bound
• Complex Problems
• Convex Hull
• Convex Set
• Communication Problems
• Post-anesthesia Care Unit
• Interior Point
• Weak Connections
• Collection Of Sets
• Rank Of Matrix
• Problem Instances
• Proof Of The Lemma
• Intersection Set
• Complementary Relationship
• Convex Polygon
• Convex Polytope
• Split Set
• Communication Protocol
• Lattice Theory