About Me Teaching Mentoring Professional Activities Publications Talks Links Bio CV (August, 2025)

Sepehr Assadi

Associate Professor, Faculty of Mathematics Research Chair

School of Computer Science, University of Waterloo

Email: [firstname] (at) [lastname] (dot) info (for general purpose)
Email: (s)[lastname] (at) uwaterloo (dot) ca (for administrative purposes at UWaterloo)
Office: DC 2334
Phone: (519) 888 4567

Research Interests: My research interest is in theoretical computer science and primarily algorithm design and complexity theory for modern models of computation. This in particular includes sublinear algorithms and lower bounds in various models for processing massive datasets, and specifically massive graphs, such as streaming, distributed, massively parallel, and sublinear time algorithms. More broadly, I am also interested in graph theory, communication complexity, online algorithms, and algorithmic game theory.

A&C Seminar: Helia Yazdanyar, and I are organizing the Algorithms & Complexity (A&C) Seminar currently (Winter 2026). Send us an email if you'd like to give a talk.

Well, that's a shame -- no picture found!
Photo courtesy of Joe Petrik

Prospective Graduate Students:

The School of Computer Science at UWaterloo offers partially-funded MS and fully-funded PhD positions with three separate application deadlines each year. You can also learn about the available positions in the A&C group here -- if you have a strong background in theoretical computer science and/or mathematics What does a strong background roughly look like? The most important factor is having mathematical maturity. Beyond that, this also includes but definitely is not limited to one or more of:

* Having done research (and possibly publications) on these topics;
* Having passed a few graduate and advanced-level undergraduate courses, or participated in reading groups on algorithms, complexity theory, combinatorics, probability, information theory, and/or algebra;
* Having participated in IOI/IMO or ACM-ICPC or similar national or international competitions;
* Having read a number of papers or followed developments in recent years on one or more area of research of your interest in TCS or Math, and can explain their significance to others. , consider applying to our graduate program and mention Algorithms and Complexity as your research interest.

I am personally not admitting new students at the moment and as such may not be able to respond to emails regarding graduate admissions.

Personal: My other half, Mina Tahmasbi Arashloo, works on Networking at University of Waterloo.

About Me

I am an Associate Professor and a Faculty of Mathematics Research Chair in the Cheriton School of Computer Science at University of Waterloo and part of the Algorithms & Complexity (A&C) Group. My primary research interests are in algorithm design and complexity theory for modern models of computation and in particular sublinear algorithms and lower bounds---broadly interpreted---for massive graph problems.

Prior to joining University of Waterloo in 2023, I was an Assistant Professor at the Computer Science Department at Rutgers University. Even before that, I spent a wonderful year as a postdoctoral researcher in Theory of Computation Group at the Computer Science Department of Princeton University, supported by the Simons Algorithms and Geometry Collaboration. I received my PhD in 2018 from the Computer & Information Science Department at University of Pennsylvania and was extremely fortunate to have Sanjeev Khanna as my advisor. My PhD thesis was on Combinatorial Optimization for Massive Datasets. During my PhD, I spent the summer of 2017 as a research intern at Google Research (NYC) with their amazing Algorithms and Optimization team. I got my B.Sc. in Computer Engineering from Sharif University of Technology.

My research has been generously supported by the Alfred P. Sloan Foundation (Sloan Research Fellowship), the Natural Sciences and Engineering Research Council of Canada (NSERC) (Discovery Grant), the Faculty of Mathematics Research Chair from University of Waterloo, the US National Science Foundation (NSF) (Faculty Early Career Development (CAREER) Award), Google Research (Research Scholar Program), and Rutgers Research Council (Fulcrum Award).

I am honored to receive the Presburger Award 2025.

A third-person bio is available here.

Teaching
Mentoring

I am very fortunate to be working/have worked with the following amazing students and postdocs:

Professional Activities
Selected Publications (Full List)

As is the convention in Theoretical Computer Science, all authorships in this list are in alphabetical order. See the [tags] below each paper for more information including full versions, videos, etc. For further details, see [DBLP] and [Google Scholar].

Semi-Streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints STOC 2026
Sepehr Assadi, Max Jiang, Mars Xiang
Summary: We reduce the problem of proving single-pass semi-streaming lower bounds for the maximum matching problem---one of the most longstanding open questions in the graph streaming literature---to a constant-size optimization problem which we call a "blueprint". This allows one to bypass all information theory and extremal graph theory (in particular RS graphs) arguments needed in prior work and focus solely on constructing better blueprints. We then use blueprints to improve prior best lower bound of 0.59-approximtion in [Kap21] to a 0.55-approximation (bonus: the paper is <1/3 in length).
Settling the Pass Complexity of Streaming Set Cover STOC 2026
Sepehr Assadi, Janani Sundaresan
Summary: Any p-pass polylog(n)-approximation for streaming set cover (m sets, n elements) requires Omgt(mn^{1/p}) space, proving the optimality of the algorithm of [HIMV16] and settling a conjecture in that work.
Better Bounds for Semi-Streaming Single-Source Shortest Paths SODA 2026
Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan
[arXiv]
Summary: Better upper and lower bounds on pass-complexity of semi-streaming algorithms for single-source (1+eps)-approximate shortest paths: O(log^2) pass algorithm and Omega(log n) pass lower bound. Previously, the upper bound was some unspecified polylog(n) and the lower bound was Omega(1). Both algorithm and lower bound are quite simple!
Distributed Triangle Detection is Hard in Few Rounds FOCS 2025
Sepehr Assadi, Janani Sundaresan
[arXiv] [talk: Janani @ TCS+]
Summary: The first multi-round lower bound for triangle detection in the distributed CONGEST model, making progress on an open question raised repeatedly in the litrature, e.g., in [ACKL20], [FKO18], and [Cen22]. The paper introduces a new round elimination technique for CONGEST that bypasses the (provable) shortcomming of previous techniques in proving any multi-round lower bounds for this problem.
Invited talk at TCS+ 2025
Vizing's Theorem in Near-Linear Time STOC 2025
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, Tianyi Zhang
[arXiv], [Conference version], [talk: Martin @ TCS+] [talk: Martin @ STOC]
Summary: A (Delta+1) edge coloring algorithm in only O(m log(Delta)) randomized time, settling the (randomized) algorithmic complexity of Vizing's theorem.
Best Paper Award at STOC'25
Invited to JACM
Invited talk at TCS+ 2024
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams SODA 2025
Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
[arXiv]
Summary: Firstly, previous upper bounds of O(log n) passes for approximating matchings in dynamic streams can be exponentially improved to O(log log n) passes. Secondly, previous lower bounds of one pass can also be improved to Omega(log log n) passes, fully settling the pass complexity of this fundamental problem. Our results have further interesting implications to models like MPC.
Invited to TALG special issue for SODA'25 papers
Faster Vizing and Near-Vizing Edge Coloring Algorithms SODA 2025
Sepehr Assadi
[arXiv], [talk: Sepehr @ Simons Institute]
Summary: A new way of solving edge coloring in general graphs by repeatedly peeling off "fair" matchings to get Delta+O(log n) coloring in near-linear randomized time. Corollary: an algorithm for (Delta+1) edge coloring in Vizing's theorem in ~O(n^2) randomized time, improving upon four-decades old bounds of O(m\sqrt{n}) time (see also the parallel work of [BCCST24] with incomparable results).
Simple Sublinear Algorithms for (Delta+1) Vertex Coloring via Asymmetric Palette Sparsification SOSA 2025
Sepehr Assadi, Helia Yazdanyar
[arXiv]
Summary: A combinatorially weaker version of palette sparsification theorem in [ACK19] still suffices for efficient sublinear algorithms for (Delta+1) coloring, but now using much simpler algorithms and analyses.
Best Paper Award at SOSA'25
Invited to TheoretiCS journal for SOSA'25 papers
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set STOC 2024 , SICOMP 2025
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
[arXiv] [Journal paper] [talk: Sepehr @ Fields Institute]
Summary: An optimal multi-pass semi-streaming lower bound for MIS, matching prior algorithms of [ACGMW15] and [GGKMR18] up to n^{o(1)} terms for any number of passes. The proof is quite general and shows how to implement a classical "round elimination" technique, modulo a crucial twist, on graphs. A key component is a new family of extremal graphs, in spirit of RS graphs, that instead of induced matchings, contain many induced copies of themselves on smaller set of vertices.
Invited to SICOMP special issue for STOC'24 papers
A Simple (1-eps)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching SOSA 2024 , TheoretiCS 2025
Sepehr Assadi
[arXiv], [Journal paper], [talk: Sepehr @ Simons Institute]
Summary: A really simple (1-eps) approximation semi-streaming algorithm for matchings in O(log(n)/eps) passes (even for weighted non-bipartite graphs), matching the state-of-the-art in [AG15], by a direct application of MWU (and without paying the typical 1/eps^2 iteration bound of "standard" MWU-based frameworks).
Invited to TheoretiCS journal for SOSA'24 papers
Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings FOCS 2023
Sepehr Assadi, Janani Sundaresan
[arXiv]
Summary: The first pass-approximation tradeoff for constant-factor approximation of semi-streaming matchings, a question dating back to the introduction of the model in [FKMSZ05]: semi-streaming (1-eps)-approximation of bipartite matching (even its size) requires Omega(log(1/eps)) passes (assuming dense RS graphs exist).
University of Waterloo Faculty of Mathematics Graduate Research Excellence Award
Rounds vs Communication Tradeoffs for Maximal Independent Sets FOCS 2022 , SICOMP 2024
Sepehr Assadi, Gillat Kol, Zhijun Zhang
[arXiv], [Conference paper] [Journal paper]
Summary: Computing maximal independent sets and matchings in the distributed sketching model---a communication model with input sharing which is "one step closer" to number-on-the-forehead communication complexity compared to number-in-hand---with sketches of size polylog(n) requires Omega(loglog(n)) rounds.
Invited to SICOMP special issue for FOCS'22 papers
An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models SOSA 2021
Sepehr Assadi, Cliff Liu, Robert E. Tarjan
[Conference paper]
Summary: An auction algorithm for bipartite matching that converges to a (1-eps)-approximation in only O(1/eps^2) iteration, each only require finding a single maximal matching. Corollary: O(1/eps^2)-pass semi-streaming algorithm and O(loglog(n)/eps^2)-round MPC algorithm for (1-eps)-approximate bipartite matching.
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms FOCS 2020
Sepehr Assadi, Ran Raz
[arXiv], [Conference paper], [talk: Sepehr @ FOCS]
Summary: The first set of near-quadratic (thus, near-optimal) lower bounds for a wide range of graph streaming problems, like reachability, shortest path, bipartite matching, even for two-pass algorithms. Only one-pass near-optimal lower bounds were known before.
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions STOC 2020 , SICOMP 2022
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh Saxena, Matt Weinberg
[arXiv], [Conference paper], [talk: Raghuvansh @ STOC]
Summary: For combinatorial auctions truthful mechanisms are indeed strictly weaker than arbitrary algorithms, when considering efficient mechanisms/algorithms, i.e., the ones with polynomial communication! In contrast, the celebrated VCG mechanism implies that with exponential communication, there is no such gap.
Invited to SICOMP special issue for STOC'20 papers
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders FOCS 2019 , SICOMP 2023
Sepehr Assadi, Sahil Singla
[arXiv], [Conference paper], [talk: Sahil @ Northwestern] [research note @ Sigecom Exchanges]
Summary: Almost exponentially improving the approximation ratio of (efficient) truthful mechanisms for m submodular bidders from O(sqrt{log m})-approximation by [Dobzinski16] to O((loglog(m))^3) approximation. This result was subsequently simplified and generalized in our work in [AKS21].
Invited to SICOMP special issue for FOCS'19 papers
Invited to Highlights Beyond EC in EC'20
Sublinear Algorithms for (Delta + 1) Vertex Coloring SODA 2019 , HALG 2020
Sepehr Assadi, Yu Chen, Sanjeev Khanna
[arXiv], [Conference paper], [talk: Sepehr @ Simons Institute], [talk: Sepehr @ HALG], [Streamlined lecture notes], [Slides], [Property testing review]
Summary: First sublinear algorithms for (Delta + 1) vertex Coloring: single-pass semi-streaming, O(n^{3/2})-time algorithm, one-round MPC algorithm, plus several lower bounds proving optimality of these results or impossibility of extensions to maximal independent sets or matchings. Key insight? palette sparsification theorem: if we sample O(log n) colors for each vertex independently from {1,..., Delta + 1}, we can properly (list-)color the graph from the sampled colors with high probability.
Best Paper Award at SODA'19
Invited to Highlights of Algorithms HALG 2020
Invited to TALG special issue for SODA'19 papers
Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation PhD Thesis @ University of Pennsylvania
Sepehr Assadi
[5-page summary], [full version]
Summary: How well can we solve a large-scale optimization problem on massive datasets in a resource-efficient manner? The focus of this thesis is on answering this question for various problems---matching, vertex cover, set cover, submodular maximization, etc.---in different modern computational models for processing massive datasets, in particular, streaming, distributed, and massively parallel computation (such as MapReduce) models.
EATCS Distinguished Dissertation Award, 2019
ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award, 2019
Morris and Dorothy Rubinoff Award for best Computer Science PhD thesis at University of Pennsylvania, 2019
Randomized Composable Coresets for Matching and Vertex Cover SPAA 2017 , HALG 2018
Sepehr Assadi, Sanjeev Khanna
[arXiv], [Conference paper], [Slides]
Summary: Randomized composable coresets? Partition edges of a graph randomly, compute a local solution on each part (a coreset), combine (or compose) the local solutions together to obtain a solution for the whole graph. Applications? Random-order streaming, MPC, distributed, etc. This work proposed this approach and obtained O(1)-approximation randomized composable coresets for matching and O(log(n))-approximation for vertex cover. These coresets were subsequently improved to (almost) 3/2-approximation and 2-approximation, respectively, in our work in [ABBMS19]
Best Paper Award at SPAA'17
Invited to Highlights of Algorithms HALG 2018
Invited to TOPC special issue for SPAA'17 papers
Combinatorial Auctions Do Need Modest Interaction EC 2017 , TEAC 2020
Sepehr Assadi
[arXiv], [Journal paper], [Conference paper], [talk: Sepehr @ EC], [Slides]
Summary: Combinatorial auctions with m items and poly(m) bidders need (almost) log(m) rounds of interaction to achieve approximately welfare-maximizing allocations (with polylog(m)-approximation), resolving an open problem of Dobzinski, Nisan, and Oren [DNO14] and Alon, Nisan, Raz, and Weinstein [ANRW15].
Invited to TEAC special issue for EC'17 papers
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem STOC 2016 , SICOMP 2021
Sepehr Assadi, Sanjeev Khanna, Yang Li
[arXiv], [Journal paper], [Conference paper], [Slides]
Summary: Approximating set cover in single-pass streams is really hard: even a crude alpha-approximation for any alpha < \sqrt{n} over m arriving sets on a universe of size n requires Omega(m*n/alpha) bits of space, matching a trivial algorithm for this problem.
Invited to SICOMP special issue for STOC'16 papers
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model SODA 2016
Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
[arXiv] (preliminary version), [Conference paper], [Slides]
Summary: Approximating matching is really harder in dynamic streams compared to insertion-only streams: the complexity of alpha-approximation on n-vertex graphs is n^2/alpha^3 up to an n^o(1) factor. This result was subsequently improved by Dark and Konrad [DK20] on the lower bound side and in my joint work with Shah [AS22] on the upper bound side to asymptotically optimal bound of Theta(n^2/alpha^3) bits.

A complete list of my publications is available here.

Talk Videos

A list of some videos of my talks that are available online:

Created by Sepehr Assadi -- Last Update: April 2025