Sepehr Assadi

According to our database, Sepehr Assadi authored at least 88 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

A Simple (1 - <i>ε</i>)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching.

Sepehr Assadi

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

2023

Recent Advances in Multi-Pass Graph Streaming Lower Bounds.

Sepehr Assadi

SIGACT News, September, 2023

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for Δ-Coloring.

Sepehr Assadi, Pankaj Kumar, Parth Mittal

TheoretiCS, 2023

Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams.

Sepehr Assadi, Gillat Kol, Zhijun Zhang

Electron. Colloquium Comput. Complex., 2023

O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set.

Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan

CoRR, 2023

Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings.

Sepehr Assadi, Janani Sundaresan

CoRR, 2023

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits.

Sepehr Assadi, Chen Wang

CoRR, 2023

A Simple (1-ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching.

Sepehr Assadi

CoRR, 2023

(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond.

Sepehr Assadi, Janani Sundaresan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On Regularity Lemma and Barriers in Streaming and Dynamic Matching.

Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Tight Bounds for Vertex Connectivity in Dynamic Streams.

Sepehr Assadi, Vihan Shah

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Tight Bounds for Monotone Minimal Perfect Hashing.

Sepehr Assadi, Martin Farach-Colton, William Kuszmaul

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling.

Sepehr Assadi, Vikram Kher, George Li, Ariel Schvartzman

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms.

Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost.

Sepehr Assadi, Vihan Shah, Chen Wang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method.

Sepehr Assadi, Aaron Bernstein, Zachary Langley

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs.

Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah

Proceedings of the 26th International Conference on Database Theory, 2023

Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings.

Sepehr Assadi, Janani Sundaresan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

On Constructing Spanners from Random Gaussian Projections.

Sepehr Assadi, Michael Kapralov, Huacheng Yu

Proceedings of the Approximation, 2023

Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance.

Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang

Proceedings of the Approximation, 2023

2022

Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions.

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

SIAM J. Comput., June, 2022

Introduction to the Special Issue on ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

Gautam Kamath, Sepehr Assadi, Anne Driemel, Janardhan Kulkarni

ACM Trans. Algorithms, 2022

Rounds vs Communication Tradeoffs for Maximal Independent Sets.

Sepehr Assadi, Gillat Kol, Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling.

Sepehr Assadi, Ariel Schvartzman

CoRR, 2022

Graph Coloring, Palette Sparsification, and Beyond (Invited Talk).

Sepehr Assadi

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring.

Sepehr Assadi, Pankaj Kumar, Parth Mittal

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic graph coloring in the streaming model.

Sepehr Assadi, Andrew Chen, Glenn Sun

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.

Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching.

Sepehr Assadi

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Spine: Scaling up Programming-by-Negative-Example for String Filtering and Transformation.

Chaoji Zuo, Sepehr Assadi, Dong Deng

Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity.

Sepehr Assadi, Chen Wang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams.

Sepehr Assadi, Vihan Shah

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions.

Sepehr Assadi, Chen Wang

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Decremental Matching in General Graphs.

Sepehr Assadi, Aaron Bernstein, Aditi Dudeja

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds.

Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, Chen Wang

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting.

Sepehr Assadi, Hoai-An Nguyen

Proceedings of the Approximation, 2022

2021

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem.

Sepehr Assadi, Sanjeev Khanna, Yang Li

SIAM J. Comput., 2021

A Two-Pass Lower Bound for Semi-Streaming Maximum Matching.

Sepehr Assadi

CoRR, 2021

Ruling Sets in Random Order and Adversarial Streams.

Sepehr Assadi, Aditi Dudeja

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma.

Sepehr Assadi, Vishvajeet N

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models.

Sepehr Assadi, S. Cliff Liu, Robert E. Tarjan

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

A Simple Semi-Streaming Algorithm for Global Minimum Cuts.

Sepehr Assadi, Aditi Dudeja

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier.

Sepehr Assadi, Thomas Kesselheim, Sahil Singla

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Beating Two-Thirds For Random-Order Streaming Matching.

Sepehr Assadi, Soheil Behnezhad

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.

Sepehr Assadi, Shay Solomon

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Graph Connectivity and Single Element Recovery via Linear and OR Queries.

Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

On the Robust Communication Complexity of Bipartite Matching.

Sepehr Assadi, Soheil Behnezhad

Proceedings of the Approximation, 2021

2020

Combinatorial Auctions Do Need Modest Interaction.

Sepehr Assadi

ACM Trans. Economics and Comput., 2020

Improved truthful mechanisms for combinatorial auctions with submodular bidders.

Sepehr Assadi, Sahil Singla

SIGecom Exch., 2020

Improved Bounds for Distributed Load Balancing.

Sepehr Assadi, Aaron Bernstein, Zachary Langley

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits.

Sepehr Assadi, Chen Wang

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Separating the communication complexity of truthful and non-truthful combinatorial auctions.

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets.

Sepehr Assadi, Gillat Kol, Rotem Oshman

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.

Sepehr Assadi, Ran Raz

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems.

Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Palette Sparsification Beyond (Δ+1) Vertex Coloring.

Noga Alon, Sepehr Assadi

Proceedings of the Approximation, 2020

2019

The Stochastic Matching Problem with (Very) Few Queries.

Sepehr Assadi, Sanjeev Khanna, Yang Li

ACM Trans. Economics and Comput., 2019

Polynomial pass lower bounds for graph streaming algorithms.

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time.

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Sublinear Algorithms for (Δ + 1) Vertex Coloring.

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Towards a Unified Theory of Sparsification for Matching Problems.

Sepehr Assadi, Aaron Bernstein

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Stochastic Submodular Cover with Limited Adaptivity.

Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Distributed and Streaming Linear Programming in Low Dimensions.

Sepehr Assadi, Nikolai Karpov, Qin Zhang

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs.

Sepehr Assadi, Xiaorui Sun, Omri Weinstein

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Secretary Ranking with Minimal Inversions.

Sepehr Assadi, Eric Balkanski, Renato Paes Leme

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.

Sepehr Assadi, Michael Kapralov, Sanjeev Khanna

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Distributed Weighted Matching via Randomized Composable Coresets.

Sepehr Assadi, MohammadHossein Bateni, Vahab S. Mirrokni

Proceedings of the 36th International Conference on Machine Learning, 2019

When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time.

Sepehr Assadi, Shay Solomon

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Fully dynamic maximal independent set with sublinear update time.

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.

Sepehr Assadi, Sanjeev Khanna

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Fast Convergence in the Double Oral Auction.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra

ACM Trans. Economics and Comput., 2017

On the rectangle escape problem.

AmirMahdi Ahmadinejad, Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Theor. Comput. Sci., 2017

SPAA 2017 Review.

Sepehr Assadi

SIGACT News, 2017

Simple Round Compression for Parallel Vertex Cover.

Sepehr Assadi

CoRR, 2017

Randomized Composable Coresets for Matching and Vertex Cover.

Sepehr Assadi, Sanjeev Khanna

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

On Estimating Maximum Matching Size in Graph Streams.

Sepehr Assadi, Sanjeev Khanna, Yang Li

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm.

Sepehr Assadi, Sanjeev Khanna, Yang Li

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem.

Sepehr Assadi

Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.

Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna

Proceedings of the 30th Conference on Learning Theory, 2017

2016

A Compile-Time Optimization Method for WCET Reduction in Real-Time Embedded Systems through Block Formation.

Morteza Mohajjel Kafshdooz, Mohammadkazem Taram, Sepehr Assadi, Alireza Ejlali

ACM Trans. Archit. Code Optim., 2016

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Algorithms for Provisioning Queries and Analytics.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen

Proceedings of the 19th International Conference on Database Theory, 2016

2015

Tight Bounds for Linear Sketches of Approximate Matchings.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

CoRR, 2015

Online Assignment of Heterogeneous Tasks in Crowdsourcing Markets.

Sepehr Assadi, Justin Hsu, Shahin Jabbari

Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, 2015

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches.

Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

The Minimum Vulnerability Problem.

Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Algorithmica, 2014

2013

On the Rectangle Escape Problem.

Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013