Please note: This PhD defence will take place in DC 2314 and online.
Parth Mittal, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sepehr Assadi
In the graph streaming model, the edges of the input graph stream by one-by-one, and the algorithm must process this stream with limited memory, which is significantly smaller than required to store the entire graph. Brooks’ Theorem states that a graph with maximum degree Δ can be Δ-colored as long as it is not a clique or an odd-cycle. We show a 1-pass, O(n * poly log n) space algorithm that can Δ-color a graph given as a stream. This is optimal up to log n factors.
In the two-party communication model, the input to some relation is split amongst two players, who work together to compute an output to the relation while minimizing the number of bits they communicate to each other. We show an O(n) communication protocol that can (Δ + 1)-color a graph. This is optimal up to constant factors.
In the pointer chasing problem, two players receive functions from [n] to [n], and wish to find the sequence of elements of [n] obtained by applying their functions alternately k times on the starting element 1. We show that any k / 1000 round communication protocol that solves this task must use Ω(n) communication. This lower bound is optimal up to factors of log n. We also show an optimal lower bound for any (k - 1) round protocol that solves a version of this problem where each value of the input functions is further obscured behind a set intersection instance.
To attend this PhD defence in person, please go to DC 2314. You can also attend virtually on Zoom.