Article contents
Pointer chasing via triangular discrimination
Published online by Cambridge University Press: 15 May 2020
Abstract
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
- Type
- Paper
- Information
- Creative Commons
- 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
- 4
- Cited by