{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T03:46:07Z","timestamp":1782186367723,"version":"3.54.5"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,5,9]],"date-time":"2013-05-09T00:00:00Z","timestamp":1368057600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00224-013-9476-x","type":"journal-article","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T03:33:19Z","timestamp":1367983999000},"page":"13-23","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Collapsing Protocol for Multiparty Pointer Jumping"],"prefix":"10.1007","volume":"54","author":[{"given":"Hongyu","family":"Liang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,5,9]]},"reference":[{"issue":"2","key":"9476_CR1","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"175","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci. 175(2), 139\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9476_CR2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02126797","volume":"8","author":"M. Ajtai","year":"1988","unstructured":"Ajtai, M.: A lower bound for finding predecessors in Yao\u2019s cell probe model. Combinatorica 8(3), 235\u2013247 (1988)","journal-title":"Combinatorica"},{"issue":"1","key":"9476_CR3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9476_CR4","first-page":"343","volume-title":"Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Andoni","year":"2008","unstructured":"Andoni, A., Indyk, P., Krauthgamer, R.: Earth mover distance over high-dimensional spaces. In: Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 343\u2013352 (2008)"},{"issue":"4","key":"9476_CR5","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s004930100009","volume":"21","author":"L. Babai","year":"2001","unstructured":"Babai, L., Hayes, T.P., Kimme, P.G.: The cost of the missing bit: communication complexity with help. Combinatorica 21(4), 455\u2013488 (2001)","journal-title":"Combinatorica"},{"key":"9476_CR6","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1007\/11523468_95","volume-title":"Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP)","author":"P. Beame","year":"2005","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower bounds for Lov\u00e1sz-Schrijver systems and beyond follow from multiparty communication complexity. In: Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), pp. 1176\u20131188 (2005)"},{"key":"9476_CR7","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Comput. Complex. 4, 350\u2013366 (1994)","journal-title":"Comput. Complex."},{"key":"9476_CR8","first-page":"210","volume-title":"Proc. 26th IEEE Conference on Computational Complexity (CCC)","author":"E. Blais","year":"2011","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. In: Proc. 26th IEEE Conference on Computational Complexity (CCC), pp. 210\u2013220 (2011)"},{"key":"9476_CR9","first-page":"379","volume-title":"Proc. 24th IEEE Conference on Computational Complexity (CCC)","author":"J. Brody","year":"2009","unstructured":"Brody, J.: The maximum communication complexity of multi-party pointer jumping. In: Proc. 24th IEEE Conference on Computational Complexity (CCC), pp. 379\u2013386 (2009)"},{"key":"9476_CR10","unstructured":"Brody, J.: Some communication complexity results and their applications. PhD thesis, Dartmouth College (2010)"},{"key":"9476_CR11","first-page":"145","volume-title":"Proc. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"J. Brody","year":"2008","unstructured":"Brody, J., Chakrabarti, A.: Sublinear communication protocols for multi-party pointer jumping and a related lower bound. In: Proc. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 145\u2013156 (2008)"},{"key":"9476_CR12","volume-title":"Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Chakrabarti","year":"2008","unstructured":"Chakrabarti, A., Jayram, T.S., P\u0103tra\u015fcu, M.: Tight lower bounds for selection in randomly ordered streams. In: Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008)"},{"key":"9476_CR13","first-page":"94","volume-title":"Proc. 15th ACM Symposium on Theory of Computing (STOC)","author":"A.K. Chandra","year":"1983","unstructured":"Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: Proc. 15th ACM Symposium on Theory of Computing (STOC), pp. 94\u201399 (1983)"},{"issue":"2","key":"9476_CR14","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/PL00001595","volume":"7","author":"C. Damm","year":"1998","unstructured":"Damm, C., Jukna, S., Sgall, J.: Some bounds on multiparty communication complexity of pointer jumping. Comput. Complex. 7(2), 109\u2013127 (1998)","journal-title":"Comput. Complex."},{"key":"9476_CR15","series-title":"LNCS.","volume-title":"Sperner Theory","author":"K. Engel","year":"2001","unstructured":"Engel, K.: Sperner Theory. LNCS. Springer, Berlin (2001)"},{"key":"9476_CR16","volume-title":"Concrete Mathematics","author":"R.L. Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison\u2013Wesley, Reading (1994)"},{"key":"9476_CR17","volume-title":"Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"A. Gronemeier","year":"2006","unstructured":"Gronemeier, A.: NOF-multiparty information complexity bounds for pointer jumping. In: Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS) (2006)"},{"key":"9476_CR18","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1007\/978-3-540-73420-8_61","volume-title":"Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP)","author":"S. Guha","year":"2007","unstructured":"Guha, S., McGregor, A.: Lower bounds for quantile estimation in random-order and multi-pass streaming. In: Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP), pp. 704\u2013715 (2007)"},{"key":"9476_CR19","first-page":"539","volume-title":"Proc. 20th ACM Symposium on Theory of Computing (STOC)","author":"M. Karchmer","year":"1988","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proc. 20th ACM Symposium on Theory of Computing (STOC), pp. 539\u2013550 (1988)"},{"key":"9476_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574948","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1996","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)"},{"key":"9476_CR21","first-page":"625","volume-title":"Proc. 26th ACM Symposium on Theory of Computing (STOC)","author":"P. Bro Miltersen","year":"1994","unstructured":"Bro Miltersen, P.: Lower bounds for union-split-find related problems on random access machines. In: Proc. 26th ACM Symposium on Theory of Computing (STOC), pp. 625\u2013634 (1994)"},{"issue":"1","key":"9476_CR22","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N. Nisan","year":"1993","unstructured":"Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. SIAM J. Comput. 22(1), 211\u2013219 (1993)","journal-title":"SIAM J. Comput."},{"key":"9476_CR23","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Lecture Notes. http:\/\/www.cs.cmu.edu\/~odonnell\/boolean-analysis\/"},{"key":"9476_CR24","volume-title":"Proc. 40th Annual ACM Symposium on Theory of Computing (STOC)","author":"R. O\u2019Donnell","year":"2008","unstructured":"O\u2019Donnell, R.: Some topics in analysis of boolean functions. In: Proc. 40th Annual ACM Symposium on Theory of Computing (STOC) (2008)"},{"issue":"3","key":"9476_CR25","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S0097539794264809","volume":"26","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P., R\u00f6dl, V., Sgall, J.: Boolean circuits, tensor ranks and communication complexity. SIAM J. Comput. 26(3), 605\u2013633 (1997)","journal-title":"SIAM J. Comput."},{"key":"9476_CR26","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1109\/FOCS.2007.34","volume-title":"Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"E. Viola","year":"2007","unstructured":"Viola, E., Wigderson, A.: One-way multi-party communication lower bound for pointer jumping with applications. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 427\u2013437 (2007)"},{"key":"9476_CR27","first-page":"209","volume-title":"Proc. 11th ACM Symposium on Theory of Computing (STOC)","author":"A.C. Yao","year":"1979","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proc. 11th ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9476-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9476-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9476-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:25Z","timestamp":1558684465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9476-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,9]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9476"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9476-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,9]]}}}