About Me Teaching Advising Professional Activities Publications Talks Links CV (January, 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 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 (currently on leave) 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 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].

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.
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).
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!
Brooks’ Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for ∆-Coloring STOC 2022
Full version in TheoretiCS 2023
Sepehr Assadi, Pankaj Kumar, Parth Mittal
[arXiv], [Journal paper], [Conference paper], [talk: Sepehr @ NUS], [talk: Parth @ STOC]
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.
Beating Two-Thirds For Random-Order Streaming Matching ICALP 2021
Sepehr Assadi, Soheil Behnezhad
[arXiv], [Conference paper], [talk: Soheil @ STOC], [talk: Soheil @ ICALP]
Summary: The 2/3-approximation random-order semi-streaming algorithm of [Bernstein20] for matchings is NOT optimal; one can get (very slightly) better approximations! At the same time, (1-ε)-approximation is also not possible for algorithms that have poly(1/ε)-space dependence in space.
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma STOC 2021
Sepehr Assadi, Vishvajeet N.
[arXiv], [Conference paper], [talk: Vishvajeet @ STOC], [Property testing review]
Summary: (1-ε)-approximation of maximum cut, matching size, connected components, and many other similar problems with polylog(n)-space streaming algorithms requires Omega(1/ε) passes even on bounded-degree planar graphs. See also the survey of [Sudan22] for connections to streaming CSPs. This improves the pass-complexity of these problems exponentially from [AKSY20], and resolves a conjecture of Verbin and Yu [VY11] (in a slightly weaker form).
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
Palette Sparsification Beyond (∆ + 1) Vertex Coloring RANDOM 2020
Noga Alon, Sepehr Assadi
[arXiv], [Conference paper], [talk: Sepehr @ RANDOM] [Property testing review]
Summary: Several extensions of the palette sparsification theorem of [ACK19] to problems like O(∆)-coloring, O(∆/ln(∆))-coloring of triangle-free graphs, and (degree+1)-coloring. Also "local" (degree-based) variant of the sparse-dense decompositions, which has been proven very useful since, e.g., in [AW22] and [HKNT22].
Invited to Theory of Computing special issue for APPROX/RANDOM 2020 papers
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
Polynomial Pass Lower Bounds for Graph Streaming Algorithms STOC 2019
Sepehr Assadi, Yu Chen, Sanjeev Khanna
[arXiv], [Conference paper], [talk: Sepehr @ Princeton]
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
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 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: September 2023