Title :
Lattices, mobius functions and communications complexity
Author :
Lovasz, Liviusz ; Saks, Michael
Author_Institution :
Dept. of Comput. Sci., Eotvos Lorand Univ., Budapest, Hungary
Abstract :
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
Keywords :
computational complexity; graph theory; combinatorial lattice theory; communications complexity; graph connectivity; lattices; mobius functions; Complexity theory; Geometry; Lattices; Polynomials; Protocols;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21924
