{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T10:23:01Z","timestamp":1787394181002,"version":"build-2736575974"},"reference-count":35,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:00:00Z","timestamp":1781827200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2801\/20"],"award-info":[{"award-number":["2801\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["800\/22"],"award-info":[{"award-number":["800\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1042\/22"],"award-info":[{"award-number":["1042\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1016\/j.tcs.2026.116134","type":"journal-article","created":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T16:27:22Z","timestamp":1782145642000},"page":"116134","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Pointer chasing with unlimited interaction"],"prefix":"10.1016","volume":"1083","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4197-015X","authenticated-orcid":false,"given":"Orr","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5065-5557","authenticated-orcid":false,"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7094-8348","authenticated-orcid":false,"given":"Tal","family":"Roth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2026.116134_bib0001","series-title":"Structural Information and Communication Complexity - 32nd International Colloquium, SIROCCO","first-page":"281","article-title":"Pointer chasing with unlimited interaction","volume":"15671","author":"Fischer","year":"2025"},{"issue":"1","key":"10.1016\/j.tcs.2026.116134_bib0002","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/0222016","article-title":"Rounds in communication complexity revisited","volume":"22","author":"Nisan","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.116134_bib0003","series-title":"Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC","first-page":"257","article-title":"A tight unconditional lower bound on distributed randomwalk computation","author":"Nanongkai","year":"2011"},{"issue":"5","key":"10.1016\/j.tcs.2026.116134_bib0004","doi-asserted-by":"crossref","first-page":"1709","DOI":"10.1137\/070683155","article-title":"Graph distances in the data-stream model","volume":"38","author":"Feigenbaum","year":"2008","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.116134_bib0005","series-title":"Proceedings of the 28th Conference on Computational Complexity, CCC","first-page":"287","article-title":"Superlinear lower bounds for multipass graph processing","author":"Guruswami","year":"2013"},{"key":"10.1016\/j.tcs.2026.116134_bib0006","series-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC","first-page":"265","article-title":"Polynomial pass lower bounds for graph streaming algorithms","author":"Assadi","year":"2019"},{"key":"10.1016\/j.tcs.2026.116134_bib0007","series-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","first-page":"542","article-title":"Matroid intersection, pointer chasing, and Young\u2019s seminormal representation of Sn","author":"Harvey","year":"2008"},{"issue":"1","key":"10.1016\/j.tcs.2026.116134_bib0008","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/jcss.1998.1577","article-title":"On data structures and asymmetric communication complexity","volume":"57","author":"Miltersen","year":"1998","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.116134_bib0009","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/j.jcss.2007.06.016","article-title":"Lower bounds for predecessor searching in the cell probe model","volume":"74","author":"Sen","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/j.tcs.2026.116134_bib0010","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","article-title":"Communication complexity","volume":"28","author":"Papadimitriou","year":"1984","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/j.tcs.2026.116134_bib0011","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/PL00001595","article-title":"Some bounds on multiparty communication complexity of pointer jumping","volume":"7","author":"Damm","year":"1998","journal-title":"Comput. Complex."},{"key":"10.1016\/j.tcs.2026.116134_bib0012","series-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","first-page":"602","article-title":"The communication complexity of pointer chasing: applications of entropy and sampling","author":"Ponzio","year":"1999"},{"key":"10.1016\/j.tcs.2026.116134_bib0013","series-title":"Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing","first-page":"644","article-title":"On quantum and probabilistic communication: Las Vegas and one-way protocols","author":"Klauck","year":"2000"},{"key":"10.1016\/j.tcs.2026.116134_bib0014","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1017\/S0963548320000085","article-title":"Pointer chasing via triangular discrimination","author":"Yehudayoff","year":"2020","journal-title":"Comb. Probab. Comput."},{"key":"10.1016\/j.tcs.2026.116134_bib0015","series-title":"16th Innovations in Theoretical Computer Science Conference, ITCS","first-page":"75:1","article-title":"Gadgetless lifting beats round elimination: improved lower bounds for pointer chasing","volume":"325","author":"Mao","year":"2025"},{"key":"10.1016\/j.tcs.2026.116134_bib0016","article-title":"Communication complexity of pointer chasing via the fixed-set lemma","volume":"abs\/2507.08919","author":"Viola","year":"2025","journal-title":"CoRR"},{"key":"10.1016\/j.tcs.2026.116134_bib0017","series-title":"Communication Complexity, and Applications","author":"Rao","year":"2020"},{"key":"10.1016\/j.tcs.2026.116134_bib0018","series-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC)","first-page":"81","article-title":"Lower bounds on communication complexity","author":"Duris","year":"1984"},{"key":"10.1016\/j.tcs.2026.116134_bib0019","series-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing","first-page":"124","article-title":"Interaction in quantum communication and the complexity of set disjointness","author":"Klauck","year":"2001"},{"key":"10.1016\/j.tcs.2026.116134_bib0020","series-title":"FST TCS Foundations of Software Technology and Theoretical Computer Science","first-page":"218","article-title":"The quantum communication complexity of the pointer chasing problem: the bit version","author":"Jain","year":"2002"},{"key":"10.1016\/j.tcs.2026.116134_bib0021","series-title":"43rd Symposium on Foundations of Computer Science FOCS","first-page":"429","article-title":"Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states","author":"Jain","year":"2002"},{"key":"10.1016\/j.tcs.2026.116134_bib0022","series-title":"Mathematical Foundations of Computer Science","first-page":"459","article-title":"NOF-Multiparty Information complexity bounds for pointer jumping","author":"Gronemeier","year":"2006"},{"key":"10.1016\/j.tcs.2026.116134_bib0023","first-page":"719","article-title":"One-way multiparty communication lower bound for pointer jumping with applications","author":"Viola","year":"2009","journal-title":"Comb."},{"key":"10.1016\/j.tcs.2026.116134_bib0024","series-title":"22nd Annual IEEE Conference on Computational Complexity (CCC)","first-page":"33","article-title":"Lower bounds for multi-player pointer jumping","author":"Chakrabarti","year":"2007"},{"key":"10.1016\/j.tcs.2026.116134_bib0025","series-title":"STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science","first-page":"145","article-title":"Sublinear communication protocols for multi-party pointer jumping and a related lower bound","author":"Brody","year":"2008"},{"key":"10.1016\/j.tcs.2026.116134_bib0026","series-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC","first-page":"379","article-title":"The maximum communication complexity of multi-party pointer jumping","author":"Brody","year":"2009"},{"key":"10.1016\/j.tcs.2026.116134_bib0027","article-title":"On total communication complexity of collapsing protocols for pointer jumping problem","volume":"abs\/1405.7596","author":"Jastrzebski","year":"2014","journal-title":"CoRR"},{"issue":"1","key":"10.1016\/j.tcs.2026.116134_bib0028","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s00224-013-9476-x","article-title":"Optimal collapsing protocol for multiparty pointer jumping","volume":"54","author":"Liang","year":"2014","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.tcs.2026.116134_bib0029","series-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM","first-page":"606","article-title":"Dependent random graphs and multi-party pointer jumping","author":"Brody","year":"2015"},{"issue":"2","key":"10.1016\/j.tcs.2026.116134_bib0030","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","article-title":"Private vs. common random bits in communication complexity","volume":"39","author":"Newman","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2026.116134_bib0031","series-title":"Communication complexity","author":"Kushilevitz","year":"1997"},{"issue":"3","key":"10.1016\/j.tcs.2026.116134_bib0032","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1137\/09075336X","article-title":"Unifying the landscape of cell-probe lower bounds","volume":"40","author":"Patrascu","year":"2011","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/j.tcs.2026.116134_bib0033","first-page":"567","article-title":"On the \u201dlog rank\u201d-conjecture in communication complexity","volume":"15","author":"Raz","year":"1995","journal-title":"Comb."},{"issue":"1","key":"10.1016\/j.tcs.2026.116134_bib0034","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1137\/15M1007525","article-title":"Lower bounds for number-in-hand multiparty communication complexity, made easy","volume":"45","author":"Phillips","year":"2016","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.116134_bib0035","series-title":"54th Annual IEEE Symposium on Foundations of Computer Science, FOCS","first-page":"668","article-title":"A tight bound for set disjointness in the message-passing model","author":"Braverman","year":"2013"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526003634?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526003634?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:25:35Z","timestamp":1787390735000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526003634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":35,"alternative-id":["S0304397526003634"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116134","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Pointer chasing with unlimited interaction","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116134","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"116134"}}