Pointer chasing via triangular discrimination
Time: Fri 2017-06-09 11.00
Location: in room 4523, Lindstedtsvägen 5
Participating: Amir Yehudayoff, Technion university
We shall see how to use information theory to prove lower bounds for the distributional communication complexity of the pointer chasing problem. A key part of the proof is using triangular discrimination instead of total variation distance; this idea may be useful elsewhere.