Communication complexity and combinatorial lattice theory

摘要

In a recent paper, Hajnal, Maass, and Turá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.