book chapter · Teubner-Texte zur Informatik · 1992

Communication Complexity and Lower Bounds for Sequential Computation

Cited by 6Abstract and details only

Abstract

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.

Cite this paper

APA 7

Kalyanasundaram, B., & Schnitger, G. (1992). Communication Complexity and Lower Bounds for Sequential Computation. Teubner-Texte zur Informatik, 253–268. https://doi.org/10.1007/978-3-322-95233-2_15

MLA 9

Kalyanasundaram, Bala, and Georg Schnitger. “Communication Complexity and Lower Bounds for Sequential Computation.” Teubner-Texte zur Informatik, 1992, pp. 253–68, https://doi.org/10.1007/978-3-322-95233-2_15.

Chicago

Kalyanasundaram, Bala, and Georg Schnitger. 1992. “Communication Complexity and Lower Bounds for Sequential Computation.” Teubner-Texte zur Informatik: 253–68. https://doi.org/10.1007/978-3-322-95233-2_15.

Harvard

Kalyanasundaram, B. and Schnitger, G. (1992) ‘Communication Complexity and Lower Bounds for Sequential Computation’, Teubner-Texte zur Informatik, pp. 253–268. Available at: https://doi.org/10.1007/978-3-322-95233-2_15.

BibTeX

@incollection{kalyanasundaram1992communication,
  title = {{Communication Complexity and Lower Bounds for Sequential Computation}},
  author = {Kalyanasundaram, Bala and Schnitger, Georg},
  booktitle = {Teubner-Texte zur Informatik},
  pages = {253--268},
  year = {1992},
  doi = {10.1007/978-3-322-95233-2_15}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.