Communication Complexity and Lower Bounds for Sequential Computation
Bala Kalyanasundaram, Georg Schnitger · Teubner-Texte zur Informatik · 1992
Information-theoretic approaches for lower bound problems are discussed and two applications of Communication Complexity are presented. The first application concerns one-tape Turing machines with an additional oneway input tape. It is shown that lower bounds on the Communication Complexity of a given language immediately imply lower bounds on the running time for this Turing machine model. Consequently, lower bounds for the Turing machine complexity of specific languages are derived. Emphasis is given to bounded-error probabilistic Turing machines, since no previous lower bounds have been obtained for this computation mode. The second application concerns a real-time comparison between Schoenhage’s Storage Modification machines and the machine model of Kolmogorov and Uspen-skii. A non-standard model of Communication Complexity is defined. It is shown that non-trivial lower bounds for this communication model will imply that Storage Modification machines cannot be simulated in real time by Kolmogorov-Uspenskii machines.