Lattices, MEbius Functions and Communication Complexity
Michael Saksl · 1988
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 combinatorial lattice theory.