Skip to main content
To KTH's start page To KTH's start page

Pointer chasing via triangular discrimination

Time: Fri 2017-06-09 11.00

Location: in room 4523, Lindstedtsvägen 5

Participating: Amir Yehudayoff, Technion university

Export to calendar

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.