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.

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

- Current courses:
- Past courses:
- CS 466/666: Algorithm Design and Analysis (Advanced Algorithms) @ UWaterloo (Fall 2023)
- CS 344: Design and Analysis of Computer Algorithms @ Rutgers (Spring 2023, Spring 2022, Spring 2021, Fall 2019)
- CS 521: Linear Programming @ Rutgers (Fall 2022)
- CS 514: Advanced Algorithms II -- Sublinear Algorithms @ Rutgers (Fall 2021, Spring 2020)
- CS 671: Graph Streaming Algorithms and Lower Bounds @ Rutgers (Fall 2020)

Advising

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

- Postdocs:
- Ariel Schvartzman (DIMACS postdoc, 2020--2022, now at Google Research in Mountain View)
- Nicole Wein (DIMACS postdoc, 2021--2023, now a Research Fellow at the Simons Institute and an Assistant Professor at the University of Michigan)
- Zihan Tan (DIMACS postdoc, 2022--)
- Prantar Ghosh (DIMACS postdoc, 2022--)

- Graduate students:
- Chen Wang (PhD, 2019--)
- Vihan Shah (PhD, 2020--)
- Janani Sundaresan (PhD, 2021--)
- Parth Mittal (PhD, 2021--)
- Chaitanya Nalam (MS @ Rutgers, 2021--2022, now a PhD student at University of Michigan)

- Undergraduate students:
- Jakob Degen (summer intern, 2020)
- Nirmit Joshi (summer intern, 2020, now a PhD student at TTIC)
- Milind Prabhu (summer intern, 2020, now a PhD student University of Michigan)
- Hoai-An Nguyen (undergraduate researcher @ Rutgers, 2022--2023, now a PhD student at CMU)
- Andrew Chen (DIMACS REU 2020, now a PhD student at Cornell)
- Glenn Sun (DIMACS REU 2021, now a PhD student at University of Washington)
- Liubov (Luba) Samborska (DIMACS REU 2022, now a PhD student at University of Michigan)
- Alexandro (Alex) Garces (DIMACS REU 2023)

Professional Activities

- Program committees:
ESA 2023, FOCS 2023, ICALP 2023, SODA 2023, ICDT 2023, RANDOM 2022, ESA 2022, STOC 2022, SODA 2022, SOSA 2022, PODC 2021, PODS 2021, ICALP 2020, SODA 2020. - Junior PCs:
EC 2022, EC 2021, COLT 2023, COLT 2021, COLT 2020. - Journal editorials:
SICOMP Special Issue of STOC 2022, TALG Special Issue of SODA 2020. - External reviewer:
- I have regularly been a sub-reviewer for most major TCS conferences including STOC, FOCS, SODA, ICALP, CCC, PODC, ITCS, as well as TCS and combinatorics journals including JACM, SICOMP, TALG, RSA, and Discrete Math.
- I have also been an external reviewer/panelist for grant agencies like National Science Foundation (NSF).

- Miscellaneous:
- Guest Reviewer for SIGACT News, review of SPAA 2017
- Co-organizer of Rutgers/DIMACS Theory of Computing Seminar (Fall 2019--Spring 2023)

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

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

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

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

On Regularity Lemma and Barriers in Streaming and Dynamic Matching
STOC 2023

[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

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

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.

Beating Two-Thirds For Random-Order Streaming Matching ICALP 2021

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

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

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

Palette Sparsification Beyond (∆ + 1) Vertex Coloring
RANDOM 2020

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

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

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

[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

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

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

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

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

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 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:

- A Simple (1−ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching Simons Workshop on Sketching and Algorithm Design, 2023
- Tutorial: Ruzsa-Szemeredi Graphs and their Applications DIMACS Workshop on Modern Techniques in Graph Algorithms, 2023
- A (Slightly) Sublinear Space Streaming Algorithm for Matchings FODSI Summer School on Sublinear Algorithms, 2022
- Tight Bounds for Monotone Minimal Perfect Hashing DIMACS Workshop on Lower Bounds and Frontiers in Data Structures, 2022
- Recent Advances in Multi-Pass Graph Streaming Lower Bounds BIRS Workshop on Communication Complexity and Applications, III, 2022
- Brooks’ Theorem in Graph Streams NUS Workshop on Algorithms and Foundations for Data Science, 2022
- On the Robust Communication Complexity of Bipartite Matching RANDOM, 2021
- Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms FOCS, 2020
- Palette Sparsification Beyond (∆ + 1) Vertex Coloring RANDOM, 2020
- Sublinear Algorithms for (∆ + 1) Vertex Coloring Highlights of Algorithms (HALG), 2020
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets PODC, 2020
- Polynomial Pass Lower Bounds in Graph Streams Princeton Theory Seminar, 2019
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling TCS+, 2019
- Sublinear Algorithms for (∆ + 1) Vertex Coloring Simons Workshop on Sublinear Algorithms and Nearest-Neighbor Search, 2018
- Combinatorial Auctions Do Need Modest Interaction EC, 2017
- The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm EC, 2017

Miscellaneous Links

- Local links @ UWaterloo:
- Local links @ Rutgers:
- Some useful links:
- Theoretical Computer Science Cheat Sheet by Steve Seiden, ACM SIGACT News 27(4):52-61, Dec. 1996
- TCS+: A series of online seminars in TCS
- Princeton TCS Seminar YouTube Channel
- Theoretical Computer Science Stack Exchange
- Math Overflow

- Some useful resources for junior PhD students and students applying to graduate schools:
- PhD Rants and Raves (Be afraid. Be very afraid.) by Y. Smaragdakis
- How to Be a Successful PhD Student (in Computer Science (in NLP/ML)) by M. Dredze and H. M. Wallach
- Does one have to be a genius to do maths? by T. Tao
- A few words on research for graduate students by F. Chung
- 3 Pieces of Reassurance for Early-Stage PhD Students (in TCS) by N. Wein
- Mathematical Writing by D. E. Knuth, T. Larrabee, and P. M. Roberts

- Some useful resources for senior PhD students and postdocs:
- Some news articles about me and my research:
- Sepehr Assadi named 2023 Faculty of Mathematics Research Chair
- Sepehr Assadi awarded 2023 Sloan Research Fellowship
- Three Rutgers Professors Named Sloan Research Fellows
- Announcing the 2021 Research Scholar Program Recipients
- The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi

Created by Sepehr Assadi -- Last Update: September 2023