ECCC-Report TR16-151https://eccc.weizmann.ac.il/report/2016/151Comments and Revisions published for TR16-151en-usMon, 26 Sep 2016 15:30:58 +0300
Paper TR16-151
| Pointer chasing via triangular discrimination |
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2016/151We 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.
Mon, 26 Sep 2016 15:30:58 +0300https://eccc.weizmann.ac.il/report/2016/151