Please note: This PhD defence will take place in DC 2314.
Janani Sundaresan, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sepehr Assadi
In this thesis, we study lower bounds in the streaming and distributed computing models for graphs. Both models arise naturally in the design of algorithms for the massive graphs that are ubiquitous in practice today.
In the streaming model, the edges of the graph arrive in an arbitrary order and must be processed without storing the entire graph. Of particular interest is the semi-streaming setting, in which the algorithm is allowed space that is near-linear in the number of vertices. The stream may be scanned multiple times, and the goal is to minimize the number of passes needed to solve the problem.
In distributed computing, each vertex acts as a computational agent and initially knows only its immediate neighborhood. Vertices communicate by sending messages along the edges of the graph. Communication proceeds in synchronous rounds: in each round, every vertex can send a (possibly different) message to each of its neighbors, receive all incoming messages, and then perform local computation. In the CONGEST model, each such message is restricted to a length logarithmic in the number of vertices. The goal is to minimize the number of rounds required to solve the problem.
We prove the following results on graphs with $n$ vertices:
- The number of passes required to find a maximal independent set in semi-streaming is $\Omega(\log \log n)$, and our result is tight by a prior algorithm. This is the first multipass lower bound for this problem.
- The number of passes required to find any $(1-\eps)$-approximation of maximum matchings is $\Omega(\log (1/\eps))$ in semi-streaming. This is the first multipass lower bound for any constant $\eps$. The current upper bound on the number of passes is $O(1/\eps^2)$. %We also prove a tight lower bound of $\Omega()$
- We prove an $\Omega(\log \log n)$ lower bound on the number of rounds required to detect a triangle in CONGEST. This is the first multi-round lower bound for this problem, and the current upper bounds are $O(n^{1/3})$ rounds.
Lower bounds in both models are proven via communication complexity: the input graph is split among multiple players who send messages to each other over a limited number of rounds. A common theme underlying all of our results is the round-elimination technique of Miltersen, Nisan, Safra, and Wigderson (1995) introduced to prove communication complexity lower bounds. Our main technical contribution is to apply this method in a range of different settings to obtain the first nontrivial multi-pass and multi-round lower bounds for these problems.