Back to search

University of Waterloo

New Techniques for Lower Bounds in Graph Streaming and Distributed Computing

Abstract

dc:description.abstract

In this dissertation, we study lower bounds in the streaming and distributed computing models for graph problems. 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 highlight three results from this dissertation for graphs with n vertices: 1) The number of passes required to find a maximal independent set in semi-streaming is Ω(log log n). Our result is tight, matching a prior algorithm. This is the first multi-pass lower bound for this problem. 2) The number of passes required to find any (1-ε)-approximation of maximum matchings is Ω(log (1/ε)) in semi-streaming. This is the first lower bound on the number of passes with a dependence on ε for any constant ε. 3) We prove an Ω(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. 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 the highlighted results is to build on and extend the round-elimination technique from communication complexity literature. Our main technical contribution is to adapt this method for a range of different settings to obtain the first nontrivial multi-pass and multi-round lower bounds for these problems.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sundaresan, Janani

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/23498

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Sundaresan, Janani. New Techniques for Lower Bounds in Graph Streaming and Distributed Computing. University of Waterloo, 2026. https://hdl.handle.net/10012/23498