Please note: This PhD seminar will take place in DC 1304 and online.
Parth Mittal, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sepehr Assadi
In the pointer chasing problem in communication complexity, two players are given functions f_A and f_B from [n] to [n] respectively, and wish to compute the last pointer in the sequence v_0 = 1, v_1 = f_A(v_0), v_2 = f_B(v_1), ... , v_k obtained by applying f_A and f_B alternately. It is easy to see that we can solve this task in O(k log n) bits of communication if we are allowed k rounds of communication. On the other hand, a series of works ended with Yehudayoff (Combin. Probab. Comput. 2020) showing that any randomized protocol using even 1 fewer round must spend Ω(n / k) communication on this problem.
In this talk, I will prove that the (k / 1000)-round randomized communication complexity of the function where the players are required to compute all the pointers in the sequence (rather than just the final one) is Ω(n). The proof uses the gadgetless lifting framework of Mao, Yang, and Zhang (ITCS 25).
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.