Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-151 | 26th September 2016 08:33

#### Pointer chasing via triangular discrimination

TR16-151
Authors: Amir Yehudayoff
Publication: 26th September 2016 15:30
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.