{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:55:09Z","timestamp":1725897309703},"publisher-location":"Wiesbaden","reference-count":37,"publisher":"Vieweg+Teubner Verlag","isbn-type":[{"type":"print","value":"9783815420331"},{"type":"electronic","value":"9783322952332"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/978-3-322-95233-2_15","type":"book-chapter","created":{"date-parts":[[2013,4,17]],"date-time":"2013-04-17T01:17:04Z","timestamp":1366161424000},"page":"253-268","source":"Crossref","is-referenced-by-count":3,"title":["Communication Complexity and Lower Bounds for Sequential Computation"],"prefix":"10.1007","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","first-page":"151","volume-title":"Lower Bounds on Information Transfer in Distributed Computations","author":"H Abelson","year":"1978","unstructured":"H. Abelson, \u201cLower Bounds on Information Transfer in Distributed Computations\u201d, Proc. 19th IEEE Symp. on Foundations of Computer Science, 1978, pp. 151\u2013158."},{"key":"15_CR2","first-page":"337","volume-title":"BPP and the Polynomial Time Hierarchy in Communication Complexity Theory","author":"L Babai","year":"1986","unstructured":"L. Babai, P. Frankl and J. Simon, \u201cBPP and the Polynomial Time Hierarchy in Communication Complexity Theory\u201d, Proc. 27th Annual IEEE Symp. on Foundations of Computer Science, 1986, pp. 337\u2013347."},{"key":"15_CR3","first-page":"1","volume-title":"Multiparty Protocols and Logspace-hard Pseudorandom Sequences","author":"L Babai","year":"1989","unstructured":"L. Babai, N. Nisan and M. Szegedy, \u201cMultiparty Protocols and Logspace-hard Pseudorandom Sequences\u201d, Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, pp. 1\u201311."},{"key":"15_CR4","first-page":"94","volume-title":"Multi-party protocols","author":"AK Chandra","year":"1983","unstructured":"A.K. Chandra, M.L. Furst and R.J. Lipton, \u201cMulti-party protocols\u201d, Proc. 15th Annual ACM Symp. on Theory of Computing, 1983, pp. 94\u201399."},{"key":"15_CR5","volume-title":"On Kolmogorov machines and related issues","author":"Y Gurevich","year":"1988","unstructured":"Y. Gurevich, \u201cOn Kolmogorov machines and related issues\u201d, Bull, of EATCS, 1988."},{"key":"15_CR6","first-page":"39","volume-title":"On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines","author":"Z Galil","year":"1986","unstructured":"Z. Galil, R. Kannan and E. Szemeredi, \u201cOn Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines\u201d, Proc. 18th Annual ACM Symp. on Theory of Computing, 1986, pp. 39\u201349."},{"key":"15_CR7","first-page":"610","volume-title":"On the Power of Small Depth Threshold Circuits","author":"J Hastad","year":"1990","unstructured":"J. Hastad and M. Goldmann, \u201cOn the Power of Small Depth Threshold Circuits\u201d, Proc. Slst Annual IEEE Symp. on Foundations of Computer Science, 1990, pp. 610\u2013618."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01704903","volume":"19","author":"JY Halpern","year":"1986","unstructured":"J.Y. Halpern, M.C. Loui, A.R. Meyer and D. Weise, \u201cOn Time Versus Space IIP\u201d, Math. Systems Theory 19, 1986, pp. 13\u201328.","journal-title":"Math. Systems Theory"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"J. Hartmanis and R.E. Stearns, \u201cOn the Computational Complexity of Algorithms\u201d, Trans. Amer. Math. Soc. , Vol. 117, 1965, pp. 285\u2013306.","journal-title":"Trans. Amer. Math. Soc."},{"key":"15_CR10","volume-title":"Ph. D. Dissertation, The Pennsylvania State University","author":"B Kalyanasundaram","year":"1988","unstructured":"B. Kalyanasundaram, \u201cLower Bounds on Time, Space and Communication\u201d, Ph. D. Dissertation, The Pennsylvania State University, Dec. 1988."},{"key":"15_CR11","first-page":"462","volume-title":"\u201cThe Art of Computer Programming\u201d, vol. 1","author":"DE Knuth","year":"1968","unstructured":"D. E. Knuth, \u201cThe Art of Computer Programming\u201d, vol. 1, Addison-Wesley, Reading Ma., 1968, pp. 462\u2013463."},{"key":"15_CR12","first-page":"41","volume-title":"The Probabilistic Communication Complexity of Set Intersection","author":"B Kalyanasundaram","year":"1987","unstructured":"B. Kalyanasundaram and G. Schnitger, \u201cThe Probabilistic Communication Complexity of Set Intersection\u201d, Proc. 2nd Annual Conference on Structure in Complexity Theory, 1987, pp. 41\u201347. To appear in SIAM J. Disc. Math."},{"key":"15_CR13","first-page":"749","volume-title":"On the Power of One-Tape Probabilistic Turing Machines","author":"B Kalyanasundaram","year":"1986","unstructured":"B. Kalyanasundaram and G. Schnitger, \u201cOn the Power of One-Tape Probabilistic Turing Machines\u201d, Proc. 24th Annual Allerton Conference on Communication, Control and Computation, 1986, pp. 749\u2013757."},{"key":"15_CR14","first-page":"217","volume":"29","author":"AN Kolmogorov","year":"1963","unstructured":"A. N. Kolmogorov and V. A. Uspenskii, \u201cOn the Definition of an Algorithm\u201d, AMS Transi 2nd series, vol. 29, 1963, pp. 217\u2013245.","journal-title":"AMS Transi"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M Karchmer","year":"1990","unstructured":"M. Karchmer and A. Wigderson, \u201cMonotone Circuits for Connectivity Require Superlogarithmic Depth\u201d, SI AM J. Disc. Math 3, 1990, pp. 255\u2013265.","journal-title":"SI AM J. Disc. Math"},{"key":"15_CR16","unstructured":"L. Lovasz, \u201cCommunication Complexity: A Survey\u201d, Tech. Report CS-TR-204\u201389, Princeton University, 1989."},{"key":"15_CR17","unstructured":"D.R. Luginbuhl and M.C. Loui, \u201cHierarchies and Space measures for pointer machines\u201d, University of Illinois at Urbana Champaign, Tech. Rep. UILU-ENG-88\u201322445."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-16486-3_101","volume":"223","author":"M Li","year":"1986","unstructured":"M. Li, L. Longpre and P.M.B. Vitanyi, \u201cOn the Power of the Queue\u201d, Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223, 1986, pp. 219\u2013223.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR19","unstructured":"M. Li and P.M.B Vitanyi, \u201cKolmogorov Complexity and its Applications\u201d, in J. van Leeuwen ed., Handbook of Theoretical Computer Science, vol. A,"},{"key":"15_CR20","first-page":"401","volume-title":"Quadratic Lower Bounds for Deterministic and Nondeterminis-tic One-Tape Turing Machines","author":"W Maass","year":"1984","unstructured":"W. Maass, \u201cQuadratic Lower Bounds for Deterministic and Nondeterminis-tic One-Tape Turing Machines\u201d, Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 401\u2013408."},{"key":"15_CR21","first-page":"94","volume-title":"Two Tapes are Better than One for Off-line Turing Machines","author":"W Maass","year":"1987","unstructured":"W. Maass, G. Schnitger and E. Szemeredi, \u201cTwo Tapes are Better than One for Off-line Turing Machines\u201d, Proc. 19th Annual ACM Symp. on Theory of Computing, 1987, 94\u2013100."},{"key":"15_CR22","volume-title":"Two Tapes are Better than One for Off-line Turing Machines","author":"W Maass","year":"1990","unstructured":"W. Maass, G. Schnitger, E. Szemeredi and G. Turan, \u201cTwo Tapes are Better than One for Off-line Turing Machines\u201d, Tech. Report CS-90\u201330, Department of Computer Science, The Pennsylvania State University, 1990."},{"key":"15_CR23","volume-title":"Complexity in Information Theory","author":"A Orlitsky","year":"1988","unstructured":"A. Orlitsky and A. El Gamal, \u201cCommunication Complexity\u201d, in Y. Abu-Mostafa ed. Complexity in Information Theory, Springer Verlag, 1988."},{"key":"15_CR24","first-page":"325","volume-title":"Proc. 2nd Internat. Conf. on Fundamentals of Computation Theory","author":"WJ Paul","year":"1979","unstructured":"W.J. Paul, \u201cKolmogorov\u2019s Complexity and Lower Bounds\u201d, in L. Budach ed., Proc. 2nd Internat. Conf. on Fundamentals of Computation Theory, Akademie Verlag, Berlin, 1979, pp. 325\u2013334."},{"key":"15_CR25","first-page":"429","volume-title":"On Determinism versus Nondeterminism and related Problems","author":"WJ Paul","year":"1983","unstructured":"W.J. Paul, N. Pippenger, E. Szemeredi and W.T. Trotter, \u201cOn Determinism versus Nondeterminism and related Problems\u201d, Proc. 24th Annual IEEE Symp. on Foundations of Computer Science 1983, pp. 429\u2013438."},{"key":"15_CR26","first-page":"343","volume-title":"Lower Bounds on the Time of Probabilistic On-line Simulations","author":"R Paturi","year":"1983","unstructured":"R. Paturi and J. Simon, \u201cLower Bounds on the Time of Probabilistic On-line Simulations\u201d, Proc. 2th Annual IEEE Symp. on Foundations of Computer Science, 1983, pp. 343\u2013350."},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0022-0000(81)90009-X","volume":"23","author":"WJ Paul","year":"1981","unstructured":"W.J. Paul, J.I. Seiferas and J. Simon, \u201cAn Information Theoretic Approach to to Time Bounds for On-line Computation\u201d, J. Comput. System Sci. 23, 1981, pp. 108\u2013126.","journal-title":"J. Comput. System Sci."},{"key":"15_CR28","first-page":"249","volume-title":"On the Distributional Complexity of Disjointness","author":"AA Razborov","year":"1990","unstructured":"A.A. Razborov, \u201cOn the Distributional Complexity of Disjointness\u201d, Proc. 17th ICALP, 1990, pp. 249\u2013253."},{"key":"15_CR29","first-page":"287","volume-title":"Monotone Circuits for Matching Require Linear Depth","author":"R Raz","year":"1990","unstructured":"R. Raz and A. Wigderson, \u201cMonotone Circuits for Matching Require Linear Depth\u201d, Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990, pp. 287\u2013292."},{"key":"15_CR30","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A Schoenhage","year":"1980","unstructured":"A. Schoenhage, \u201cStorage Modification Machines\u201d, SIAM J. Comput., 9, 1980, pp. 490\u2013508.","journal-title":"SIAM J. Comput."},{"key":"15_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-94701-7","volume-title":"Rekursive Funktionen und ihre Komplexitaet","author":"CP Schnorr","year":"1974","unstructured":"C. P. Schnorr, \u201cRekursive Funktionen und ihre Komplexitaet\u201d, Teubner, Stuttgart, 1974."},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"RE Tarjan","year":"1979","unstructured":"R. E. Tarjan, \u201cA Class of Algorithms Which Require Nonlinear Time to Maintain Disjoint Sets\u201d, J. Comput. System Sci. 18, 1979, pp. 110\u2013127.","journal-title":"J. Comput. System Sci."},{"key":"15_CR33","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"RE Tarjan","year":"1983","unstructured":"R. E. Tarjan, \u201cData Structures and Network Algorithms\u201d, SIAM, 1983, page 2."},{"key":"15_CR34","first-page":"81","volume-title":"Area-Time Complexity for VLSI","author":"CD Thompson","year":"1979","unstructured":"C. D. Thompson, \u201cArea-Time Complexity for VLSI\u201d, Proc. 11th Annual ACM Symp. on Theory of Computing 1979, pp. 81\u201388."},{"key":"15_CR35","unstructured":"P. Van Emde Boas, \u201cSpace Measures for Storage Modification Machines\u201d, University of Amsterdam, Tech. Rep. FVI-UVA-87\u201316. To appear in Information Processing Letters."},{"key":"15_CR36","first-page":"209","volume-title":"Some Complexity Questions Related to Distributed Computing","author":"AC Yao","year":"1979","unstructured":"A.C. Yao, \u201cSome Complexity Questions Related to Distributed Computing\u201d, Proc. 11th Annual ACM Symp. on Theory of Computing, 1979, pp. 209\u2013213."},{"key":"15_CR37","first-page":"420","volume-title":"Lower Bounds by Probabilistic Arguments","author":"AC Yao","year":"1983","unstructured":"A.C. Yao, \u201cLower Bounds by Probabilistic Arguments\u201d, Proc. 24th Annual IEEE Symp. on Foundations of Computer Science, 1983, pp. 420\u2013428."}],"container-title":["TEUBNER-TEXTE zur Informatik","Informatik"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-322-95233-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T06:38:35Z","timestamp":1557643115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-322-95233-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783815420331","9783322952332"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-322-95233-2_15","relation":{},"ISSN":["1615-4584"],"issn-type":[{"type":"print","value":"1615-4584"}],"subject":[],"published":{"date-parts":[[1992]]}}}