{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:40:08Z","timestamp":1747867208027,"version":"3.41.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031917356","type":"print"},{"value":"9783031917363","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91736-3_17","type":"book-chapter","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:02:49Z","timestamp":1747864969000},"page":"281-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pointer Chasing with\u00a0Unlimited Interaction"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4197-015X","authenticated-orcid":false,"given":"Orr","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5065-5557","authenticated-orcid":false,"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7094-8348","authenticated-orcid":false,"given":"Tal","family":"Roth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","unstructured":"Assadi, S., Chen, Y., Khanna, S.: Polynomial pass lower bounds for graph streaming algorithms. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 265\u2013276 (2019). https:\/\/doi.org\/10.1145\/3313276.3316361","DOI":"10.1145\/3313276.3316361"},{"key":"17_CR2","doi-asserted-by":"publisher","unstructured":"Brody, J.: The maximum communication complexity of multi-party pointer jumping. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC, pp. 379\u2013386 (2009). https:\/\/doi.org\/10.1109\/CCC.2009.30","DOI":"10.1109\/CCC.2009.30"},{"key":"17_CR3","doi-asserted-by":"publisher","unstructured":"Brody, J., Chakrabarti, A.: Sublinear communication protocols for multi-party pointer jumping and a related lower bound. In: STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, pp. 145\u2013156 (2008). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2008.1341","DOI":"10.4230\/LIPIcs.STACS.2008.1341"},{"key":"17_CR4","doi-asserted-by":"publisher","unstructured":"Brody, J., Sanchez, M.: Dependent random graphs and multi-party pointer jumping. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM, pp. 606\u2013624 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.606","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.606"},{"key":"17_CR5","doi-asserted-by":"publisher","unstructured":"Chakrabarti, A.: Lower bounds for multi-player pointer jumping. In: 22nd Annual IEEE Conference on Computational Complexity (CCC), pp. 33\u201345 (2007). https:\/\/doi.org\/10.1109\/CCC.2007.14","DOI":"10.1109\/CCC.2007.14"},{"issue":"2","key":"17_CR6","doi-asserted-by":"publisher","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":"17_CR7","doi-asserted-by":"publisher","unstructured":"Duris, P., Galil, Z., Schnitger, G.: Lower bounds on communication complexity. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 81\u201391. ACM (1984). https:\/\/doi.org\/10.1145\/800057.808668","DOI":"10.1145\/800057.808668"},{"issue":"5","key":"17_CR8","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J Feigenbaum","year":"2008","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM J. Comput. 38(5), 1709\u20131727 (2008). https:\/\/doi.org\/10.1137\/070683155","journal-title":"SIAM J. Comput."},{"key":"17_CR9","doi-asserted-by":"publisher","unstructured":"Gronemeier, A.: NOF-multiparty information complexity bounds for pointer jumping. In: Mathematical Foundations of Computer Science, pp. 459\u2013470 (2006). https:\/\/doi.org\/10.1007\/11821069_40","DOI":"10.1007\/11821069_40"},{"key":"17_CR10","doi-asserted-by":"publisher","unstructured":"Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. In: Proceedings of the 28th Conference on Computational Complexity, CCC, pp. 287\u2013298 (2013). https:\/\/doi.org\/10.1109\/CCC.2013.37","DOI":"10.1109\/CCC.2013.37"},{"key":"17_CR11","unstructured":"Harvey, N.J.A.: Matroid intersection, pointer chasing, and young\u2019s seminormal representation of $$S_{\\text{n}}$$. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 542\u2013549 (2008)"},{"key":"17_CR12","doi-asserted-by":"publisher","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In: 43rd Symposium on Foundations of Computer Science FOCS, pp. 429\u2013438 (2002). https:\/\/doi.org\/10.1109\/SFCS.2002.1181967","DOI":"10.1109\/SFCS.2002.1181967"},{"key":"17_CR13","doi-asserted-by":"publisher","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: The quantum communication complexity of the pointer chasing problem: The bit version. In: FST TCS Foundations of Software Technology and Theoretical Computer Science, pp. 218\u2013229 (2002). https:\/\/doi.org\/10.1007\/3-540-36206-1_20","DOI":"10.1007\/3-540-36206-1_20"},{"key":"17_CR14","unstructured":"Jastrzebski, M.: On total communication complexity of collapsing protocols for pointer jumping problem. CoRR abs\/1405.7596 (2014). http:\/\/arxiv.org\/abs\/1405.7596"},{"key":"17_CR15","doi-asserted-by":"publisher","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 644\u2013651 (2000). https:\/\/doi.org\/10.1145\/335305.335396","DOI":"10.1145\/335305.335396"},{"key":"17_CR16","doi-asserted-by":"publisher","unstructured":"Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum communication and the complexity of set disjointness. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp. 124\u2013133. ACM (2001). https:\/\/doi.org\/10.1145\/380752.380786","DOI":"10.1145\/380752.380786"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"1","key":"17_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00224-013-9476-x","volume":"54","author":"H Liang","year":"2014","unstructured":"Liang, H.: Optimal collapsing protocol for multiparty pointer jumping. Theory Comput. Syst. 54(1), 13\u201323 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9476-x","journal-title":"Theory Comput. Syst."},{"key":"17_CR19","doi-asserted-by":"publisher","unstructured":"Mao, X., Yang, G., Zhang, J.: Gadgetless lifting beats round elimination: improved lower bounds for pointer chasing. In: 16th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol.\u00a0325, pp. 75:1\u201375:14 (2025). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2025.75","DOI":"10.4230\/LIPICS.ITCS.2025.75"},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/JCSS.1998.1577","volume":"57","author":"PB Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. 57(1), 37\u201349 (1998). https:\/\/doi.org\/10.1006\/JCSS.1998.1577","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR21","doi-asserted-by":"publisher","unstructured":"Nanongkai, D., Sarma, A.D., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC, pp. 257\u2013266 (2011). https:\/\/doi.org\/10.1145\/1993806.1993853","DOI":"10.1145\/1993806.1993853"},{"issue":"1","key":"17_CR22","doi-asserted-by":"publisher","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."},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Sipser, M.: Communication complexity. J. Comput. Syst. Sci. 28(2), 260\u2013269 (1984). https:\/\/doi.org\/10.1016\/0022-0000(84)90069-2","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"17_CR24","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M Patrascu","year":"2011","unstructured":"Patrascu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40(3), 827\u2013847 (2011). https:\/\/doi.org\/10.1137\/09075336X","journal-title":"SIAM J. Comput."},{"key":"17_CR25","doi-asserted-by":"publisher","unstructured":"Ponzio, S., Radhakrishnan, J., Venkatesh, S.: The communication complexity of pointer chasing: applications of entropy and sampling. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 602\u2013611 (1999). https:\/\/doi.org\/10.1145\/301250.301413","DOI":"10.1145\/301250.301413"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"Rao, A., Yehudayoff, A.: Communication Complexity, and Applications. Cambridge University Press (2020)","DOI":"10.1017\/9781108671644"},{"issue":"4","key":"17_CR27","first-page":"567","volume":"15","author":"R Raz","year":"1995","unstructured":"Raz, R., Spieker, B.: On the \u201clog rank\u2019\u2019-conjecture in communication complexity. Comb. 15(4), 567\u2013588 (1995)","journal-title":"Comb."},{"issue":"3","key":"17_CR28","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/J.JCSS.2007.06.016","volume":"74","author":"P Sen","year":"2008","unstructured":"Sen, P., Venkatesh, S.: Lower bounds for predecessor searching in the cell probe model. J. Comput. Syst. Sci. 74(3), 364\u2013385 (2008). https:\/\/doi.org\/10.1016\/J.JCSS.2007.06.016","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR29","doi-asserted-by":"publisher","unstructured":"Viola, E., Wigderson, A.: One-way multiparty communication lower bound for pointer jumping with applications. Comb. 719\u2013743 (2009). https:\/\/doi.org\/10.1007\/s00493-009-2667-z","DOI":"10.1007\/s00493-009-2667-z"},{"key":"17_CR30","doi-asserted-by":"publisher","unstructured":"Yehudayoff, A.: Pointer chasing via triangular discrimination. Comb. Probab. Comput. 485\u2013494 (2020). https:\/\/doi.org\/10.1017\/S0963548320000085","DOI":"10.1017\/S0963548320000085"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91736-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:02:55Z","timestamp":1747864975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91736-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031917356","9783031917363"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91736-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delphi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.torontomu.ca\/sirocco-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}