{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:53:49Z","timestamp":1764784429753},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T00:00:00Z","timestamp":1589500800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove an essentially sharp <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000085_inline1.png\" \/><jats:tex-math>\n$\\tilde \\Omega (n\/k)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> lower bound on the <jats:italic>k<\/jats:italic>-round distributional complexity of the <jats:italic>k<\/jats:italic>-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson\u2019s <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000085_inline2.png\" \/><jats:tex-math>\n$\\tilde \\Omega (n\/{k^2})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> lower bound, and essentially matches the randomized lower bound proved by Klauck. The proof is information-theoretic, and a key part of it is using asymmetric triangular discrimination instead of total variation distance; this idea may be useful elsewhere.<\/jats:p>","DOI":"10.1017\/s0963548320000085","type":"journal-article","created":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T06:23:46Z","timestamp":1589523826000},"page":"485-494","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":10,"title":["Pointer chasing via triangular discrimination"],"prefix":"10.1017","volume":"29","author":[{"given":"Amir","family":"Yehudayoff","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,5,15]]},"reference":[{"key":"S0963548320000085_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.016"},{"key":"S0963548320000085_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"S0963548320000085_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/090747270"},{"key":"S0963548320000085_ref20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1731"},{"key":"S0963548320000085_ref19","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. System Sci."},{"key":"S0963548320000085_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103463"},{"key":"S0963548320000085_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808717"},{"key":"S0963548320000085_ref12","doi-asserted-by":"crossref","first-page":"1970","DOI":"10.1109\/TIT.2007.896888","article-title":"Interaction in quantum communication","volume":"53","author":"Klauck","year":"2007","journal-title":"IEEE Trans. Inform. Theory"},{"key":"S0963548320000085_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.37"},{"key":"S0963548320000085_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808668"},{"key":"S0963548320000085_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/18.850703"},{"key":"S0963548320000085_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993853"},{"key":"S0963548320000085_ref14","volume-title":"Communication Complexity","author":"Kushilevitz","year":"2006"},{"key":"S0963548320000085_ref5","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019543"},{"key":"S0963548320000085_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.85"},{"key":"S0963548320000085_ref10","unstructured":"[10] Khot, S. (2002) On the power of unique 2-prover 1-round games. In 34th Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 767\u2013775."},{"key":"S0963548320000085_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225093"},{"key":"S0963548320000085_ref18","first-page":"549","article-title":"A functional analysis proof of Gromov\u2019s polynomial growth theorem","author":"Ozawa","year":"2018","journal-title":"Ann. Sci. De L\u2019ENS"},{"key":"S0963548320000085_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335396"},{"key":"S0963548320000085_ref8","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2577"},{"key":"S0963548320000085_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/100811969"},{"key":"S0963548320000085_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOP934"},{"key":"S0963548320000085_ref4","volume-title":"Elements of Information Theory","author":"Cover","year":"2012"},{"key":"S0963548320000085_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001595"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T13:33:55Z","timestamp":1602596035000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000085\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,15]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["S0963548320000085"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000085","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution license (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}