{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:25:23Z","timestamp":1725456323752},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634379"},{"type":"electronic","value":"9783540695479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029950","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T01:24:59Z","timestamp":1133400299000},"page":"71-84","source":"Crossref","is-referenced-by-count":4,"title":["Communication complexity and sequential computation"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Abelson, H., Lower bounds on information transfer in distributed computations. Proc. 19th Annual Symp. on Foundations of Computer Science, 151\u2013158, 1978.","DOI":"10.1109\/SFCS.1978.22"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Ullman, J.D., Yannakakis, M., On notions of informations transfer in VLSI circuits. Proc. 15th Annual ACM Symp. on Theory of Computing, 133\u2013139, 1983.","DOI":"10.1145\/800061.808742"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Nisan, N., Szegedy, M., Multiparty protocols and logspace-hard pseudo-random sequences. Proc. 21st Annual ACM Symp. on Theory of Computing, 1\u201311, 1989.","DOI":"10.1145\/73007.73008"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Beame, P., A general sequential time-space trade-off for finding unique elements. Proc. 21st Annual ACM Symp. on Theory of Computing, 197\u2013203, 1989.","DOI":"10.1145\/73007.73026"},{"key":"7_CR5","unstructured":"Cobham, A., The intrinsic computational difficulty of functions. Proc. 1964 Congress for Logic, Mathematics and Philosophy of Science, North Holland, 24\u201330, 1964."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., The linear-array problem in communication complexity resolved. To appear in Proc. 29th Annual ACM Symp. on Theory of Computing, 1997.","DOI":"10.1145\/258533.258622"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0304-3975(96)00062-X","volume":"168","author":"M. Dietzfelbinger","year":"1996","unstructured":"Dietzfelbinger, M., Hromkovic, J., Schnitger, G., A comparison of two lower bounds methods for communication complexity. Theo. Comp. Sci. 168 (1), 39\u201351, 1996.","journal-title":"Theo. Comp. Sci."},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(91)90175-2","volume":"82","author":"M. Dietzfelbinger","year":"1991","unstructured":"Dietzfelbinger, M., Maass, W., Schnitger, G., The complexity of matrix transposition on one-tape Turing machines. Theoretical Computer Science, 82(1), 113\u2013129, 1991.","journal-title":"Theoretical Computer Science"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"\u010euri\u0161 P., Hromkovi\u010d, J., Rolim, J., Schnitger, G., Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. Proc. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 1200, Springer-Verlag,117\u2013128, 1997.","DOI":"10.1007\/BFb0023453"},{"key":"7_CR10","unstructured":"Gurevich, Y., On Kolmogorov machines and related issues. Bulletin of the European Association for Theoretical Computer Science, 1988."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Gr\"oger, H.D., Turan, G., On linear decision trees computing Boolean Functions. Proc. 18th International Colloquium on Automata, Languages and Programming, 707\u2013718, 1991.","DOI":"10.1007\/3-540-54233-7_176"},{"key":"7_CR12","unstructured":"Gr\"oger, H.D., Turan, G., A linear lower bound for the size of threshold circuits. Bulletin of the European Association for Theoretical Computer Science. 1993."},{"key":"7_CR13","unstructured":"Hopkroft, J.E., Ullman, J.D., Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Relation between Chomsky hierarchy and communication complexity hierarchy. Acta Math. Univ. Com. (48\u201349), 311\u2013317, 1986.","DOI":"10.1016\/0304-3975(86)90087-3"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer-Verlag 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Schnitger, G., The probabilistic communication complexity of set intersection. SIAM J. on Discrete Math. 5(4), 1992.","DOI":"10.1137\/0405044"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Schnitger, G., Communication complexity and lower bounds for sequential machines. In: Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, Teubner Verlag, 840\u2013849, 1992.","DOI":"10.1007\/978-3-322-95233-2_15"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth, SIAM J. on Disc. Math., 718\u2013727, 1990.","DOI":"10.1137\/0403021"},{"key":"7_CR19","first-page":"217","volume":"30","author":"A. N. Kolmogorov","year":"1963","unstructured":"Kolmogorov, A. N., Uspenskij, V. A., On the definition of an algorithm. Russian Math. Surveys 30, 217\u2013245, 1963.","journal-title":"Russian Math. Surveys"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Kushilevitz E., Nisan N., Communication Complexity. Cambridge University Press 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Lengauer, Th., VLSI Theory. In: Handbook of Theoretical Computer Science, Vol. A, Algorithms and Complexity, Elsevier, 835\u2013868, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50021-7"},{"key":"7_CR22","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-16486-3_101","volume":"223","author":"M. Li","year":"1986","unstructured":"Li, M., Longpre, L., Vitanyi, P.M.B., On the Power of the Queue. Structure in Complexity Theory, Lecture Notes in Computer Science, vol. 223, 219\u2013223, 1986.","journal-title":"Lecture Notes in Computer Science"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Maass, W., Quadratic lower bounds for deterministic and nondeterministic one-Tape Turing machines. Proc. 16th Annual ACM Symp. on Theory of Computing, 401\u2013408, 1984.","DOI":"10.1145\/800057.808706"},{"key":"7_CR24","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/BF01275490","volume":"3","author":"W. Maass","year":"1993","unstructured":"Maass, W., Schnitger, G., Szemeredi, E., Turan, G., Two tapes are better than one for off-line Turing machines. Computational Complexity 3, 392\u2013401, 1993.","journal-title":"Computational Complexity"},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"Lipton, R. J., Tarjan, R. E., Applications of a planar separator theorem. SIAM J. Computing 9, 615\u2013627, 1980.","journal-title":"SIAM J. Computing"},{"key":"7_CR26","first-page":"235","volume-title":"Paths, Flow and VLSI Layout","author":"L. Lov\u00e1sz","year":"1990","unstructured":"Lov\u00e1sz, L., Communication Complexity: A Survey. In: Paths, Flow and VLSI Layout (Korte, LovAsz, Pr\"omel, and Schrijver, eds.), Springer-Verlag, 235\u2013266, Berlin 1990."},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E., Las Vegas is better than determinism in VLSI and distributed computing. Proc. 14th Annual ACM Symp. on Theory of Computing, 330\u2013337, 1982.","DOI":"10.1145\/800070.802208"},{"issue":"2","key":"7_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"Micali, S., Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Information Processing Letters 12(2), 103\u2013105, 1981.","journal-title":"Information Processing Letters"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Lower bounds for union-split-find related related problems on random access machines. Proc. 26th Annual ACM Symp. on Theory of Computing, 625\u2013634, 1994.","DOI":"10.1145\/195058.195415"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A., On data structures and asymmetric communication complexity. Proc. 27th Annual ACM Symp. on Theory of Computing, 103\u2013111, 1995.","DOI":"10.1145\/225058.225093"},{"key":"7_CR31","unstructured":"Nisan, N., The communication complexity of threshold gates. Technical Report, Dept. of Comp. Sci., Hebrew Univ., 1994."},{"key":"7_CR32","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"N. Nisan","year":"1995","unstructured":"Nisan, N., Wigderson, A.: On rank versus communication complexity. Combinatorica 15, 557\u2013565, 1995.","journal-title":"Combinatorica"},{"key":"7_CR33","unstructured":"Orlitsky, A., El Gamal, A., Communication Complexity, In: Complexity in Information Theory (Y. Abu-Mostafa, ed.), Springer-Verlag 1988."},{"issue":"3","key":"7_CR34","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"R. Raz","year":"1992","unstructured":"Raz, R., Wigderson, A., Monotone circuits for matching require linear depth, J. of the ACM 39(3), 736\u2013744, 1992.","journal-title":"J. of the ACM"},{"issue":"2","key":"7_CR35","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"Razborov A.A., On the distributed complexity of disjointness, Theo. Comput. Sci. 106(2), 385\u2013390, 1992.","journal-title":"Theo. Comput. Sci."},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Roychowdhury, V.P., Orlitzky, Sin K.Y., Lower bounds on threshold and related circuits via communication complexity. IEEE Transactions on Information Theory, 1994.","DOI":"10.1109\/18.312169"},{"key":"7_CR37","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. A. Sch\u00f6nhage","year":"1980","unstructured":"Sch\u00f6nhage, A. A., Storage modification machines. SIAM J. Computing 9, 490\u2013508, 1980.","journal-title":"SIAM J. Computing"},{"key":"7_CR38","unstructured":"Thompson, C.D., A complexity theory for VLSI, Doctoral dissertation. CMU-CS80-140, Computer Science Department, Carnegie-Mellon University, Pittsburgh, August 1980."},{"key":"7_CR39","doi-asserted-by":"crossref","unstructured":"Turan, G., On the complexity of planar Boolean circuits. Computational Complexity, 1995.","DOI":"10.1007\/BF01277954"},{"key":"7_CR40","unstructured":"Ullman, J. D., Computational Aspects of VLSI. Computer Science Press, 1984."},{"key":"7_CR41","unstructured":"Wigderson, A., Information theoretic reasons for computational difficulty or communication complexity for circuit complexity. Proc. of the International Congress of Mathematicians, 1537\u20131548, 1990."},{"issue":"3","key":"7_CR42","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M. Yannakakis","year":"1991","unstructured":"Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. of Comput. Syst. Sci. 43(3), 441\u2013466, 1991.","journal-title":"J. of Comput. Syst. Sci."},{"key":"7_CR43","doi-asserted-by":"crossref","unstructured":"Yao, A. C., Some complexity questions related to distributive computing. Proc. 11th Annual ACM Symp. on Theory of Computing, 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"},{"key":"7_CR44","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"Yao, A.C., Should tables be sorted? J. of ACM 28, 615\u2013628, 1981.","journal-title":"J. of ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:22:46Z","timestamp":1586578966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/bfb0029950","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}