Sepehr Assadi
Assistant Professor Department of Computer Science, Rutgers University
Email: firstname (dot) lastname (at) rutgers (dot) edu
Office: CoRE 310
I am an assistant professor in the Computer Science Department
at Rutgers University and part of the
Theory of Computing Group.
Prior to that, I spent a wonderful year as a postdoctoral researcher at Princeton University
supported by the Simons Algorithms and Geometry Collaboration. I received my PhD from the department of Computer & Information Science at University of Pennsylvania
and was extremely fortunate to have Sanjeev Khanna as my advisor.
I got my B.Sc. in Computer Engineering from Sharif University of Technology, Iran.
Research Interests:
My primary research interest is in theoretical foundations of big data analysis. This in particular includes sublinear algorithms and lower bounds
in various models of computation for processing massive datasets such as streaming, distributed communication, massively parallel
computation, and sublinear time algorithms. More broadly, I am also interested in algorithmic graph theory, communication complexity, online algorithms, and
algorithmic game theory.
Prospective Students:
I am not actively looking for PhD students at the moment; however, if you are a highly motivated student with a strong background in theoretical computer science and mathematics, and if you are interested in working with me, apply to our
PhD Program and
mention my name in your application.

Teaching
Professional Activities
- • Program Commitees: PODC 2021, PODS 2021, ICALP 2020, SODA 2020
- • Journal editorial: TALG Special Issue of SODA 2020
- • Co-organizer of Rutgers/DIMACS Theory of Computing Seminar (Fall 2019--present)
Students
I am very fortunate to be working with the following amazing students:
- Chen Wang (PhD, 2019--)
- Vihan Shah (PhD, 2020--)
- Janani Sundaresan (PhD, 2021--)
- Chaitanya Sai Krishna (MS, 2020--)
- Jakob Degen (summer intern, 2020)
Publications
Click on each title for a summary of the paper, drafts, presentation slides, videos, etc. For further details, see [DBLP] and [Google Scholar]
- Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier SODA 2021
- A Simple Semi-Streaming Algorithm for Global Minimum Cuts SOSA 2021
- An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models SOSA 2021
- Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms FOCS 2020
- Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems FOCS 2020
-
Improved Bounds for Distributed Load Balancing
DISC 2020
Best Paper Award at DISC'20
- Palette Sparsification Beyond (∆ + 1) Vertex Coloring RANDOM 2020
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets PODC 2020
- Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits STOC 2020
-
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
STOC 2020
Invited to SICOMP special issue for STOC'20 papers
- Secretary Ranking with Minimal Inversions NeurIPS 2019
-
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
FOCS 2019
Invited to SICOMP special issue for FOCS'19 papersInvited to Highlights Beyond EC in EC'20
- Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs PODC 2019
- Distributed Weighted Matching via Randomized Composable Coresets ICML 2019
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ICALP 2019
- Distributed and Streaming Linear Programming in Low Dimensions PODS 2019
- Polynomial Pass Lower Bounds for Graph Streaming Algorithms STOC 2019
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ITCS 2019
-
Sublinear Algorithms for (∆ + 1) Vertex Coloring
SODA 2019 and HALG 2020
Invited to Highlights of Algorithms HALG 2020Best Paper Award at SODA'19
- Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs SODA 2019
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time SODA 2019
- Stochastic Submodular Cover with Limited Adaptivity SODA 2019
- Towards a Unified Theory of Sparsification for Matching Problems SOSA 2019
-
Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation
PhD Thesis
EATCS Distinguished Dissertation Award, 2019Rubinoff Dissertation Award for Best Computer Science PhD Thesis at University of Pennsylvania, 2019
- Fully Dynamic Maximal Independent Set with Sublinear Update Time STOC 2018
- Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem SODA 2018
-
Randomized Composable Coresets for Matching and Vertex Cover
SPAA 2017 and HALG 2018
Invited to Highlights of Algorithms HALG 2018Invited to TOPC special issue for SPAA'17 papers
- Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons COLT 2017
-
Combinatorial Auctions Do Need Modest Interaction
EC 2017
Full version in TEAC special issue for EC'17 papers
-
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
EC 2017
Miscellaneous
- • Local links:
- • Some useful resources for early-year 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
- • A Wordcloud of my publications topics:
- • Local links: