Communication complexity and combinatorial lattice theory (Q1309387)

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.