About Me Teaching Advising Professional Activities Publications Talks Links CV (August, 2024)

Sepehr Assadi

Associate Professor, Faculty of Mathematics Research Chair

Cheriton 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.

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

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

CS department at UWaterloo offers fully-funded MS and PhD positions with three separate application deadlines each year. You can also learn about the available positions in the A&C group here.

Interested specifically in working with me and my team and 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. ? Submit an application to our graduate program and mention my name.
If you have read some of my papers and can concisely articulate your interest on working on those topics for your graduate studies, feel free to contact me directly. Unfortunately, I may not be able to respond to any other types of emails regarding graduate admissions.

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. I am also on the faculty of Computer Science Department at Rutgers University (Visiting Professor) and an affiliated member of DIMACS. 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.

Previously, 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 the recipient of EATCS Distinguished Dissertation Award, ACM-EATCS Principles of Distributed Computing Dissertation Award, and Rubinoff Dissertation Award. 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 Natural Sciences and Engineering Research Council of Canada (NSERC) (Discovery Grant), the Alfred P. Sloan Foundation (Sloan Research Fellowship), the Faculty of Mathematics Research Chair from University of Waterloo, the National Science Foundation (NSF) (Faculty Early Career Development (CAREER) Award: CCF-2047061), Google Research (Research Scholar Program), and Rutgers Research Council (Fulcrum Award).

Teaching
Advising

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].

Vizing’s Theorem in Near-Linear Time arXiv 2024
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martın Costa, Shay Solomon, Tianyi Zhang
[arXiv]
Summary: A (Delta+1) edge coloring algorithm in only O(m log(Delta)) randomized time, settling the (randomized) algorithmic complexity of Vizing's theorem.
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.
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
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
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set STOC 2024
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
[arXiv]
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−ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching SOSA 2024
Sepehr Assadi
[arXiv], [talk: Sepehr @ Simons Institute]
Summary: A really simple (1-ε) approximation semi-streaming algorithm for matchings in O(log(n)/ε) 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/ε^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-ε)-approximation of bipartite matching (even its size) requires Omega(log(1/ε)) passes (assuming dense RS graphs exist).
University of Waterloo Faculty of Mathematics Graduate Research Excellence Award
On Regularity Lemma and Barriers in Streaming and Dynamic Matching STOC 2023
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
[arXiv], [Conference paper], [talk: Sepehr @ FODSI summer school], [talk: Sanjeev @ Princeton], [talk: Huan @ STOC]
Summary: The first better-than-2 approximation algorithm for matchings in single-pass streams and dynamic graphs with non-trivial guarantees (albeit only slightly). The trick? Use regularity lemma (and other tools from extremal graph theory) to sparsify the graph. The result in streaming is in some sense as good as it gets: better space bounds would imply better RS graph upper bounds.
Tight Bounds for Monotone Minimal Perfect Hashing SODA 2023
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
[arXiv], [Conference paper], [talk: Sepehr @ DIMACS]
Summary: Improving the lower bound of Monotone Minimal Perfect Hashing from Omega(n) bits to an optimal Omega(n*logloglog(n)) bits(!), matching a construction of Belazzougui, Boldi, Pagh, Vigna [BBPV09], and settling a longstanding open question in that work.
Invited to TALG special issue for SODA'23 papers
Rounds vs Communication Tradeoffs for Maximal Independent Sets FOCS 2022
Full version in 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
Deterministic Graph Coloring in the Streaming Model STOC 2022
Sepehr Assadi, Andrew Chen, Glenn Sun
[arXiv], [Conference paper], [talk: Glenn @ STOC], [Property testing review]
Summary: There is a single-pass semi-streaming algorithm that can color any graph of max-degree ∆ with (∆ + 1) colors [ACK19]. This algorithm is randomized but what about deterministic algorithms? We prove that even exp(∆^o(1)) colors do not suffice for single-pass semi-streaming algorithms that are deterministic!
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-ε)-approximation in only O(1/ε^2) iteration, each only require finding a single maximal matching. Corollary: O(1/ε^2)-pass semi-streaming algorithm and O(loglog(n)/ε^2)-round MPC algorithm for (1-ε)-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.
Improved Bounds for Distributed Load Balancing DISC 2020
Sepehr Assadi, Aaron Bernstein, Zach Langley
[arXiv], [Conference paper], [talk: Zach @ DISC]
Summary: A distributed CONGEST algorithm for O(1)-approximation of load-balancing problem (a.k.a semi-matchings) in poly(log n) rounds. The algorithm works even for weighted graphs but in the more relaxed LOCAL model.
Best Paper Award at DISC'20
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions STOC 2020
Full version in 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
Full version in 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 (∆ + 1) Vertex Coloring SODA 2019 and 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 (∆ + 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,...,∆ + 1}, we can still properly (list-)color the graph only 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
Towards a Unified Theory of Sparsification for Matching Problems SOSA 2019
Sepehr Assadi, Aaron Bernstein
[arXiv], [Conference paper], [Slides]
Summary: Edge-degree constrained subgraph (EDCS) of [BS15] can be used as a natural matching sparsifier in different scenarios, leading to (almost) 3/2-approximation in one-way communication complexity, stochastic matching, and fault-tolerant matching.
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 and 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 (co-winner)
Invited to Highlights of Algorithms HALG 2018
Invited to TOPC special issue for SPAA'17 papers
Combinatorial Auctions Do Need Modest Interaction EC 2017
Full version in 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
Full version in 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: August 2024