Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-151 | 26th September 2016 08:33

Pointer chasing via triangular discrimination

RSS-Feed




TR16-151
Authors: Amir Yehudayoff
Publication: 26th September 2016 15:30
Downloads: 2674
Keywords: 


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. A key part of the proof is using triangular discrimination instead of total variation distance; this idea may be useful elsewhere.



ISSN 1433-8092 | Imprint