Janani Sundaresan, a PhD candidate at the Cheriton School of Computer Science, has been awarded a Faculty of Mathematics Graduate Research Excellence Award. Conferred annually to two graduate students who have authored or coauthored an outstanding research paper, the prestigious recognition comes with a prize of $5,000.
Janani’s paper titled “Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings” was co-authored with her doctoral advisor Professor Sepehr Assadi. It was presented at FOCS 2023, the 64th IEEE Symposium on Foundations of Computer Science, one of the two top international conferences in theoretical computer science.
Left to right: Janani Sundaresan and Sepehr Assadi
Janani Sundaresan is a PhD student in the computer science theory group at the Cheriton School of Computer Science. She is interested in sublinear and streaming algorithms, online algorithms and more broadly optimization problems. Recently, she has focused on proving lower bounds for streaming algorithms.
Sepehr Assadi is an Associate Professor and a Faculty of Mathematics Research Chair at the Cheriton School of Computer Science. His research interest is in theoretical computer science and primarily algorithm design and complexity theory for modern models of computation. This includes sublinear algorithms and lower bounds in various models for processing massive datasets such as streaming, distributed, massively parallel, and sublinear time algorithms. He is also interested in graph theory, communication complexity, online algorithms, and algorithmic game theory.
Janani’s paper makes substantial progress on a longstanding open question regarding the maximum matching problem in the semi-streaming model. The maximum matching problem is the problem of finding the largest number of edges in a given graph that do not share any vertices. As an application, consider finding a pairing of a set of items to a set of interested buyers in a way that each buyer receives at most one item and each item is allocated to at most one buyer. This application can be modelled as an instance of the maximum matching problem on a graph between items and buyers, with edges showing which buyer is interested in which item. The maximum matching problem has been a cornerstone of algorithmic research for almost a century, including pioneering work by Jack Edmonds and William Tutte, mathematicians both formerly affiliated with the University of Waterloo.
The semi-streaming model is a model of computation tailored toward processing massive graphs.
In the classical view of algorithms, often referred to as the von Neumann model, we assume that our algorithms have random-access to every part of the input at a unit cost. This model, however, can be unrealistic when working with inputs that are too large to be stored in the main memory of the computer. Instead, in such scenarios, one typically only has sequential access to the input — say, stored in the hard-drive of the computer which allows a fast sequential access but a slow random access — and needs to process it with a memory much smaller than the input size — say, corresponding to the main memory of the computer, which is typically much smaller than its hard-drive. The semi-streaming model precisely captures this scenario. Specifically, a semi-streaming algorithm needs to process its input by making one or a few passes over the edges of the input graph and use a limited memory, proportional only to the number of vertices in the graph as opposed to the potentially much larger number of edges.
Janani’s paper now considers the following question: does finding even a near-optimal maximum matching in the semi-streaming model require making a substantial number of passes over the input? Stated more formally, the paper asks how many passes are needed to find a (1 + ϵ)-approximation of maximum matching as a function of ϵ.
Given the central role of the maximum matching problem in algorithm design and its wide range of applications, this problem has received significant attention since the introduction of the semi-streaming model almost two decades ago. Yet, almost no progress has been made on the open question except for one- or two-pass algorithms. Janani’s paper, on the other hand, proves the following result:
Any semi-streaming algorithm for finding a (1+ϵ)-approximation of maximum matching requires Ω (log (1/ϵ)) passes, even for ϵ = θ(1). The lower bound holds assuming a natural combinatorial hypothesis regarding the density of the so-called Ruzsa-Szemeredi graphs in extremal graph theory.
Consequently, while we might still not know the optimal pass-dependence on the parameter ϵ, this is the first time that we have any evidence toward necessity of any dependence at all on this parameter, Professor Assadi explained.
“To put this result in perspective, before Janani’s work, we only knew that maximum matching cannot be solved in one or two passes over the input,” Professor Assadi said. “Thus, it was entirely conceivable that this problem could have been solved by making, say, just three passes over the input, regardless of how accurate an approximate solution we aimed for. On the other hand, Janani’s result now proves that, under a natural combinatorial hypothesis, no constant number of passes, say, even a hundred or a thousand, suffices for solving this problem, as long as we require a sufficiently accurate solution.”
To learn more about this award-winning research, please see Sepehr Assadi and Janani Sundaresan, “Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings,” 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 2023, pp. 909–932.
