Recognized for groundbreaking work on lower bounds in multi-pass streaming algorithms
Professor Sepehr Assadi has won the 2025 Presburger Award, a prestigious honour recognizing his exceptional contributions to theoretical computer science. The honour specifically acknowledges his pioneering work on establishing lower bounds for multi-pass streaming algorithms, a long-standing and challenging problem in the field.
Since 2010, the European Association for Theoretical Computer Science has conferred the Presburger Award annually to a young scientist who has made outstanding contributions in theoretical computer science, documented by a published paper or series of papers. The award is named in honour of Mojżesz Presburger, who conducted pioneering research on the decidability of the theory of addition, work that is now known as Presburger arithmetic.
“Congratulations to Sepehr on receiving this year’s Presburger Award,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “Since joining us in July 2023, he has received a steady stream of prestigious recognitions for his research excellence — a 2023 Sloan Research Fellowship, a Faculty of Mathematics Research Chair, the Faculty’s 2025 Golden Jubilee Research Excellence Award, along with recent best paper awards at SOSA 2025 and STOC 2025.”
Sepehr Assadi is an Associate Professor 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. As of July 2025, his papers have been cited collectively more than 2,500 times, with an h-index of 30 according to Google Scholar.
Lower bounds in multi-pass graph streaming
Multi-pass graph streaming algorithms process large graphs by making multiple passes over a stream of their edges. These algorithms aim to solve graph problems efficiently while using minimal memory and as few passes over the data as possible. The central goal in the study of these algorithms is to determine the optimal trade-offs between the number of passes and the space complexity needed for solving various graph problems.
Understanding multi-pass streaming algorithms not only has direct applications to processing massive datasets in practice, but also reveals rich connections between this model and other areas of computer science. The challenges in understanding this model have made it one of the most important frontiers of research to better understand fundamental time- and space-complexity trade-offs in complexity theory.
Multi-pass graph streaming lower bounds, in particular, have proven to be remarkably hard to obtain. For most fundamental problems of interest studied in this model — such as maximal independent set, minimum spanning tree, and maximum matching — no non-trivial lower bounds were known on the space complexity of any p-pass streaming algorithms whenever p is greater than 1. Indeed, until very recently, proving any multi-pass lower bounds for almost any problem of interest appeared as a significant barrier, which requires new ideas and techniques.
Starting from 2019, Professor Assadi has been leading the research toward shattering this barrier. This research direction involved developing techniques for proving first non-trivial lower bounds for multi-pass graph streaming algorithms in his earlier work and has since matured to even establish optimal lower bounds for several problems of interest in this model:
- Maximal independent set: With Christian Konrad, Kheeran Naidu, Professor Assadi and his PhD student Janani Sundaresan established the first non-trivial multi-pass lower bound for the maximal independent set problem, a lower bound that is also optimal, thus fully settling the complexity of this fundamental problem.
- Approximate maximum matching: In work with Soheil Behnezhad, Christian Konrad, Kheeran Naidu and Janani Sundaresan, Professor Assadi and his collaborators obtained not only the first non-trivial lower bound for approximating the maximum matching problem, but also improved decades-old algorithms to obtain optimal bounds for this problem.
- Minimum spanning tree: In collaboration with Gillat Kol and Zhijun Zhang, Professor Assadi gave the first multi-pass lower bound for the minimum spanning tree problem over dynamic streams. Once again, this lower bound is optimal.
These new lower bounds all required significant new conceptual and technical innovations. In particular, the proofs of the first two results have been obtained by developing a new technique, called hierarchical embedding, which provides a novel way to combine combinatorial and information-theoretic constructions for obtaining strong round-elimination arguments in the multi-party communication complexity model.