{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:44:57Z","timestamp":1725486297623},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540416951"},{"type":"electronic","value":"9783540446934"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44693-1_18","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T05:10:18Z","timestamp":1181625018000},"page":"206-217","source":"Crossref","is-referenced-by-count":4,"title":["On Multipartition Communication Complexity"],"prefix":"10.1007","author":[{"given":"Pavol","family":"\u010euri\u0161","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stasys","family":"Jukna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Sauerhoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,3,16]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, A non-linear time lower bound for Boolean branching programs, Proc. of 40th FOCS, 1999, pp. 60\u201370.","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudl\u00e1k, V. R\u00f6dl, E. Szemeredi, and Gy. Tur\u00e1n, Two lower bounds for branching programs, in: Proc. 18th ACM STOC, 1986, pp. 30\u201338.","DOI":"10.1145\/12130.12134"},{"key":"18_CR3","unstructured":"P. Beame, M. Saks, X. Sun, and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, Technical Report 25, Electr. Coll. on Comp. Compl., 2000."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"P. Beame, M. Saks, and J. S. Thathachar, Time-space tradeoffs for branching programs, in: Proc. of 39th FOCS, 1998, pp. 254\u2013263.","DOI":"10.1109\/SFCS.1998.743453"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov, and R. Smolensky, On lower bounds for read-k-times branching programs, Computational Complexity 3 (1993), pp. 1\u201318.","journal-title":"Computational Complexity"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, and G. Tur\u00e1n, On the communication complexity of graph properties, in: Proc. of 20th ACM STOC, 1988, pp. 186\u2013191.","DOI":"10.1145\/62212.62228"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, Communication Complexity and Parallel Computing, EATCS Texts in Theoretical Computer Science, Springer-Verlag, 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"18_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-46541-3_12","volume-title":"Proc. of STACS 2000","author":"J. Hromkovi\u010d","year":"2000","unstructured":"J. Hromkovi\u010d and M. Sauerhoff, Tradeoffs between nondeterminism and complexity for communication protocols and branching programs, in: Proc. of STACS 2000, LNCS 1770, pp. 145\u2013156."},{"issue":"1","key":"18_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1051\/ita\/1995290100751","volume":"29","author":"S. Jukna","year":"1995","unstructured":"S. Jukna, A note on read-k-times branching programs, RAIRO Theor. Inf. and Applications 29:1 (1995), pp. 75\u201383.","journal-title":"RAIRO Theor. Inf. and Applications"},{"issue":"3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(98)00042-0","volume":"85","author":"S. Jukna","year":"1998","unstructured":"S. Jukna and A. Razborov, Neither reading few bits twice nor reading illegally helps much, Discrete Appl. Math. 85:3 (1998), pp. 223\u2013238.","journal-title":"Discrete Appl. Math"},{"key":"18_CR11","unstructured":"S. Jukna and G. Schnitger, On the complexity of graphs which lack small cliques, manuscript."},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"18_CR13","unstructured":"F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1998."},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"I. Newman, Private vs. common random bits in communication complexity, Information Processing Letters 39 (1991), pp. 67\u201371.","journal-title":"Information Processing Letters"},{"issue":"1","key":"18_CR15","first-page":"152","volume":"3","author":"E. A. Okol\u2019nishnikova","year":"1998","unstructured":"E. A. Okol\u2019nishnikova, On Lower Bounds for Branching Programs, Siberian Advances in Mathematics 3:1 (1998), pp. 152\u2013166.","journal-title":"Siberian Advances in Mathematics"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"Ch. H. Papadimitriou","year":"1984","unstructured":"Ch. H. Papadimitriou and M. Sipser, Communication complexity, J. Comput. Syst. Sci. 28 (1984), pp. 260\u2013269.","journal-title":"J. Comput. Syst. Sci"},{"key":"18_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Proc. of FCT\u2019 91","author":"A. Razborov","year":"1991","unstructured":"A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, in: Proc. of FCT\u2019 91, Lecture Notes in Computer Science 529, Springer-Verlag 1991, pp. 47\u201360."},{"key":"18_CR18","unstructured":"A. Yao, The entropic limitations of VLSI computations, in: Proc. 13th ACM STOC (1981), pp. 308\u2013311."}],"container-title":["Lecture Notes in Computer Science","STACS 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44693-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:29:51Z","timestamp":1556501391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44693-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540416951","9783540446934"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44693-1_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}