Sepehr Assadi
Associate Professor, Faculty of Mathematics Research Chair
Cheriton School of Computer Science, University of Waterloo
Email: | [firstname] (at) [lastname] (dot) info |
|
Email: | (s)[lastname] (at) uwaterloo (dot) ca |
|
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.
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.
I am very fortunate to be working/have worked with the following amazing students and postdocs:
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].
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
SODA 2025
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
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).
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
STOC 2024
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
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
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
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
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
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
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!
Brooks’ Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for ∆-Coloring
STOC 2022
Full version in TheoretiCS 2023
Summary:
A single-pass semi-streaming algorithm for ∆-coloring of any graph with maximum degree ∆ (as long it is not a clique nor an odd cycle and so is ∆-colorable); in other words, a semi-streaming
Brooks' theorem.
An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models
SOSA 2021
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
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
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
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
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
Polynomial Pass Lower Bounds for Graph Streaming Algorithms STOC 2019
Summary:
Breaking the so-called logarithmic barrier and providing the first polynomial pass lower bound for ANY semi-streaming problem which is not "too hard",
i.e., has an O(n) communication protocol---the problem is lexicographically first maximal independent set. Similar lower bounds for max flow with
exponential edge capacities.
Sublinear Algorithms for (∆ + 1) Vertex Coloring
SODA 2019 and HALG 2020
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
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
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
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
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
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
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.