Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T17:44:37.709Z Has data issue: false hasContentIssue false
  • English
  • Français

Pointer chasing via triangular discrimination

Part of: Theory of computing Communication, information

Published online by Cambridge University Press:  15 May 2020

Amir Yehudayoff
Amir Yehudayoff*
Affiliation:
Department of Mathematics, Technion – Israel Institute of Technology, Haifa32000, Israel, Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove an essentially sharp $\tilde \Omega (n/k)$ lower bound on the k-round distributional complexity of the k-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson’s $\tilde \Omega (n/{k^2})$ 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.

MSC classification

Primary: 68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Secondary: 94A05: Communication theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 4 , July 2020 , pp. 485 - 494
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
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.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

†

Research supported by ISF.

References

Barak, B., Braverman, M., Chen, X. and Rao, A. (2013) How to compress interactive communication. SIAM J. Comput. 42 1327–1363.CrossRefGoogle Scholar
Benjamini, I., Duminil-Copin, H., Kozma, G. and Yadin, A. (2015) Disorder, entropy and harmonic functions. Ann. Probab. 43 2332–2373.CrossRefGoogle Scholar
Braverman, M., Rao, A., Weinstein, O. and Yehudayoff, A. (2013) Direct products in communication complexity. In 54th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 746–755.CrossRefGoogle Scholar
Cover, T. M. and Thomas, J. A. (2012) Elements of Information Theory, Wiley.Google Scholar
Csiszár, I. and Shields, P. C. (2004) Information Theory and Statistics: A Tutorial, Now Publishers.CrossRefGoogle Scholar
Damm, C., Jukna, S. and Sgall, J. (1998) Some bounds on multiparty communication complexity of pointer jumping. Comput. Complex. 7 109–127.CrossRefGoogle Scholar
Duris, P., Galil, Z. and Schnitger, G. (1984) Lower bounds on communication complexity. In 16th Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 81–91.CrossRefGoogle Scholar
Erschler, A. and Karlsson, A. (2010) Homomorphisms to r constructed from random walks. Ann. Inst. Fourier 60 2095–2113.CrossRefGoogle Scholar
Guruswami, V. and Onak, K. (2013) Superlinear lower bounds for multipass graph processing. In 2013 IEEE Conference on Computational Complexity (CCC), IEEE, pp. 287–298.CrossRefGoogle Scholar
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–775.Google Scholar
Klauck, H. (2000) On quantum and probabilistic communication: Las Vegas and one-way protocols. In 32nd Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 644–651.CrossRefGoogle Scholar
Klauck, H., Nayak, A., Ta-Shma, A. and Zuckerman, D. (2007) Interaction in quantum communication. IEEE Trans. Inform. Theory 53 1970–1982.Google Scholar
Klawe, M., Paul, W. J., Pippenger, N. and Yannakakis, M. (1984) On monotone formulae with restricted depth. In 16th Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 480–487.CrossRefGoogle Scholar
Kushilevitz, E. and Nisan, N. (2006) Communication Complexity, Cambridge University Press.Google Scholar
Miltersen, P. B., Nisan, N., Safra, S. and Wigderson, A. (1995) On data structures and asymmetric communication complexity. In 27th Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 103–111.CrossRefGoogle Scholar
Nanongkai, D., Das Sarma, A. and Pandurangan, G. (2011) A tight unconditional lower bound on distributed random walk computation. In 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 257–266.CrossRefGoogle Scholar
Nisan, N. and Wigderson, A. (1991) Rounds in communication complexity revisited. In 23rd Annual ACM Symposium on Theory of Computing (STOC), ACM, pp. 419–429.CrossRefGoogle Scholar
Ozawa, N. (2018) A functional analysis proof of Gromov’s polynomial growth theorem. Ann. Sci. De L’ENS 549–556.Google Scholar
Papadimitriou, C. H. and Sipser, M. (1984) Communication complexity. J. Comput. System Sci. 28 260–269.Google Scholar
Ponzio, S. J., Radhakrishnan, J. and Venkatesh, S. (2001) The communication complexity of pointer chasing. J. Comput. System Sci. 62 323–355.CrossRefGoogle Scholar
Raz, R. (2011) A counterexample to strong parallel repetition. SIAM J. Comput. 40 771–777.CrossRefGoogle Scholar
Razborov, A. A. (1992) On the distributional complexity of disjointness. Theoret. Comput. Sci. 106 385–390.CrossRefGoogle Scholar
Sen, P. and Venkatesh, S. (2008) Lower bounds for predecessor searching in the cell probe model. J. Comput. System Sci. 74 364–385.CrossRefGoogle Scholar
Topsøe, F. (2000) Some inequalities for information divergence and related measures of discrimination. IEEE Trans. Inform. Theory 46 1602–1609.CrossRefGoogle Scholar