{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:29Z","timestamp":1742600429155,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_52","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:05:11Z","timestamp":1330290311000},"page":"643-654","source":"Crossref","is-referenced-by-count":1,"title":["Some bounds on multiparty communication complexity of pointer jumping"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Damm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stasys","family":"Jukna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"52_CR1","unstructured":"A. Ambainis. Improving the unexpected: Upper bounds on communication complexity. Manuscript, 1994."},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Kimmel, and S. V. Lokam. Simultaneous messages vs. communication. In Proc. of the 12th STACS, LNCS 900, pages 361\u2013372. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-59042-0_88"},{"key":"52_CR3","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45:204\u2013232, 1992.","journal-title":"J. Comput. Syst. Sci."},{"key":"52_CR4","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel and J. Tarui. On ACC. Comput. Complexity, 4:350\u2013366, 1994.","journal-title":"Comput. Complexity"},{"key":"52_CR5","unstructured":"B. Bollig, M. Sauerhoff, D. Sieling, and I. Wegener. On the power of different types of restricted branching programs. Technical Report TR94-026, Electronic Colloquium on Computational Complexity, 1994."},{"key":"52_CR6","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, M. L. Furst, and R. J. Lipton. Multi-party protocols. In Proc. of the 15th STOC, pages 94\u201399. ACM, 1983.","DOI":"10.1145\/800061.808737"},{"issue":"1","key":"52_CR7","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/0406009","volume":"6","author":"F. R. K. Chung","year":"1993","unstructured":"F. R. K. Chung and P. Tetali. Communication complexity and quasi-randomness. SIAM J. Disc. Math., 6(1):110\u2013123, 1993.","journal-title":"SIAM J. Disc. Math."},{"key":"52_CR8","unstructured":"C. Damm and S. Jukna. On multiparty games for pointer jumping. Forschungsbericht Nr. 95-09, Universit\u00e4t Trier, Mathematik\/Informatik, 1995."},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(87)90037-X","volume":"73","author":"P. \u010euri\u0161","year":"1987","unstructured":"P. \u010euri\u0161, Z. Galil, and G. Schnitger. Lower bounds on communication complexity. Inf. Comput., 73:1\u201322, 1987.","journal-title":"Inf. Comput."},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"M. Grigni and M. Sipser. Monotone separation of logspace from NC 1. In Proc. of the 6th Structure in Complexity Theory, pages 294\u2013298, IEEE, 1991.","DOI":"10.1109\/SCT.1991.160272"},{"key":"52_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J. H\u00e5stad","year":"1991","unstructured":"J. H\u00e5stad and M. Goldmann. On the power of small-depth threshold circuits. Comput. Complexity, 1:113\u2013129, 1991.","journal-title":"Comput. Complexity"},{"key":"52_CR12","unstructured":"E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, to appear."},{"issue":"1","key":"52_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N. Nisan","year":"1993","unstructured":"N. Nisan and A. Wigderson. Rounds in communication complexity revisited. SIAM J. Comput., 22(1):211\u2013219, 1993.","journal-title":"SIAM J. Comput."},{"key":"52_CR14","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and M. Sipser. Communication complexity. J. Comput. Syst. Sci., 28:260\u2013269, 1984.","journal-title":"J. Comput. Syst. Sci."},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"P. Pudl\u00e1k and V. R\u00f6dl. Modified ranks of tensors and the size of circuits. In Proc. of the 25th STOC, pages 523\u2013531. ACM, 1993.","DOI":"10.1145\/167088.167228"},{"key":"52_CR16","unstructured":"P. Pudl\u00e1k, V. R\u00f6dl, and J. Sgall. Boolean circuits, tensor ranks and communication complexity. To appear in SIAM J. Comput."},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Graph-theoretic arguments in low level complexity. In Proc. of the 6th MFCS, LNCS 53, pages 162\u2013176. Springer-Verlag, 1977.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"52_CR18","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. On ACC and threshold circuits. In Proc. of the 31st FOCS, pages 619\u2013627. IEEE, 1990.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:11:07Z","timestamp":1742598667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}