Sepehr Assadi

ORCID

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 146

Top Venues

Publications

Sepehr Assadi, Chen Wang
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits. COLT (2024)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. STOC (2024)
Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. CoRR (2024)
Sepehr Assadi, Sanjeev Khanna
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. CoRR (2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. CCC (2024)
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. STOC (2024)
Sepehr Assadi
Faster Vizing and Near-Vizing Edge Coloring Algorithms. CoRR (2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. CoRR (2024)
Sepehr Assadi
)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching. SOSA (2024)
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. PODS (2023)
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
Tight Bounds for Monotone Minimal Perfect Hashing. SODA (2023)
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set. CoRR (2023)
Sepehr Assadi, Vihan Shah, Chen Wang
Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost. NeurIPS (2023)
Sepehr Assadi, Janani Sundaresan
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond. CoRR (2023)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. ITCS (2023)
Sepehr Assadi, Janani Sundaresan
Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings. FOCS (2023)
Sepehr Assadi, Vikram Kher, George Li, Ariel Schvartzman
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling. EC (2023)
Sepehr Assadi
A Simple (1-ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching. CoRR (2023)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams. Electron. Colloquium Comput. Complex. (2023)
Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah
Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. ICDT (2023)
Sepehr Assadi
Recent Advances in Multi-Pass Graph Streaming Lower Bounds. SIGACT News 54 (3) (2023)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. CoRR (2023)
Sepehr Assadi, Chen Wang
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits. CoRR (2023)
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. APPROX/RANDOM (2023)
Sepehr Assadi, Janani Sundaresan
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond. STOC (2023)
Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah
Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. CoRR (2023)
Sepehr Assadi, Pankaj Kumar, Parth Mittal
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for Δ-Coloring. TheoretiCS 2 (2023)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC (2023)
Sepehr Assadi, Michael Kapralov, Huacheng Yu
On Constructing Spanners from Random Gaussian Projections. APPROX/RANDOM (2023)
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. CoRR (2023)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams. CoRR (2023)
Sepehr Assadi, Janani Sundaresan
Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings. CoRR (2023)
Sepehr Assadi, Vihan Shah
Tight Bounds for Vertex Connectivity in Dynamic Streams. SOSA (2023)
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
Tight Bounds for Monotone Minimal Perfect Hashing. CoRR (2022)
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
Decremental Matching in General Graphs. CoRR (2022)
Sepehr Assadi, Pankaj Kumar, Parth Mittal
Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring. STOC (2022)
Sepehr Assadi, Hoai-An Nguyen
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. APPROX/RANDOM (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. CoRR (2022)
Sepehr Assadi, Vihan Shah
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. ITCS (2022)
Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space. SODA (2022)
Sepehr Assadi, Chen Wang
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. ITCS (2022)
Sepehr Assadi
Graph Coloring, Palette Sparsification, and Beyond (Invited Talk). DISC (2022)
Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, Chen Wang
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. COLT (2022)
Gautam Kamath, Sepehr Assadi, Anne Driemel, Janardhan Kulkarni
Introduction to the Special Issue on ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020. ACM Trans. Algorithms 18 (4) (2022)
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
Decremental Matching in General Graphs. ICALP (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. Electron. Colloquium Comput. Complex. (2022)
Sepehr Assadi, Michael Kapralov, Huacheng Yu
On Constructing Spanners from Random Gaussian Projections. CoRR (2022)
Sepehr Assadi, Andrew Chen, Glenn Sun
Deterministic graph coloring in the streaming model. STOC (2022)
Sepehr Assadi, Hoai-An Nguyen
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. CoRR (2022)
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions. SIAM J. Comput. 51 (3) (2022)
Sepehr Assadi
A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching. SODA (2022)
Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab S. Mirrokni, Chen Wang
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. CoRR (2022)
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. CoRR (2022)
Sepehr Assadi, Ariel Schvartzman
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling. CoRR (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. FOCS (2022)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR (2022)
Sepehr Assadi, Chen Wang
Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity. NeurIPS (2022)
Sepehr Assadi, Pankaj Kumar, Parth Mittal
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for Δ-Coloring. CoRR (2022)
Chaoji Zuo, Sepehr Assadi, Dong Deng
Spine: Scaling up Programming-by-Negative-Example for String Filtering and Transformation. SIGMOD Conference (2022)
Sepehr Assadi, Vihan Shah
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. CoRR (2022)
Sepehr Assadi, Vihan Shah
Tight Bounds for Vertex Connectivity in Dynamic Streams. CoRR (2022)
Sepehr Assadi, S. Cliff Liu, Robert E. Tarjan
An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models. SOSA (2021)
Sepehr Assadi, Aditi Dudeja
Ruling Sets in Random Order and Adversarial Streams. DISC (2021)
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
Graph Connectivity and Single Element Recovery via Linear and OR Queries. ESA (2021)
Sepehr Assadi, Soheil Behnezhad
On the Robust Communication Complexity of Bipartite Matching. APPROX-RANDOM (2021)
Sepehr Assadi, Vishvajeet N
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. STOC (2021)
Sepehr Assadi, Chen Wang
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. CoRR (2021)
Sepehr Assadi, Vishvajeet N
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma. CoRR (2021)
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier. SODA (2021)
Sepehr Assadi, Andrew Chen, Glenn Sun
Deterministic Graph Coloring in the Streaming Model. CoRR (2021)
Sepehr Assadi
A Two-Pass Lower Bound for Semi-Streaming Maximum Matching. CoRR (2021)
Sepehr Assadi, Sanjeev Khanna, Yang Li
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. SIAM J. Comput. 50 (3) (2021)
Sepehr Assadi, Soheil Behnezhad
Beating Two-Thirds For Random-Order Streaming Matching. ICALP (2021)
Sepehr Assadi, Soheil Behnezhad
Beating Two-Thirds For Random-Order Streaming Matching. CoRR (2021)
Sepehr Assadi, Shay Solomon
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach. CoRR (2021)
Sepehr Assadi, Shay Solomon
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach. ESA (2021)
Sepehr Assadi, Aditi Dudeja
A Simple Semi-Streaming Algorithm for Global Minimum Cuts. SOSA (2021)
Noga Alon, Sepehr Assadi
Palette Sparsification Beyond (Δ+1) Vertex Coloring. CoRR (2020)
Sepehr Assadi, Sahil Singla
Improved truthful mechanisms for combinatorial auctions with submodular bidders. SIGecom Exch. 18 (1) (2020)
Noga Alon, Sepehr Assadi
Palette Sparsification Beyond (Δ+1) Vertex Coloring. APPROX-RANDOM (2020)
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier. CoRR (2020)
Sepehr Assadi, Chen Wang
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits. CoRR (2020)
Sepehr Assadi, Gillat Kol, Rotem Oshman
Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets. PODC (2020)
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions. CoRR (2020)
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
Graph Connectivity and Single Element Recovery via Linear and OR Queries. CoRR (2020)
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
Separating the communication complexity of truthful and non-truthful combinatorial auctions. STOC (2020)
Sepehr Assadi, Ran Raz
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. CoRR (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. CoRR (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. FOCS (2020)
Sepehr Assadi, Shay Solomon
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time. CoRR (2020)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
Improved Bounds for Distributed Load Balancing. CoRR (2020)
Sepehr Assadi, Ran Raz
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. FOCS (2020)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
Improved Bounds for Distributed Load Balancing. DISC (2020)
Sepehr Assadi, Chen Wang
Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. STOC (2020)
Sepehr Assadi
Combinatorial Auctions Do Need Modest Interaction. ACM Trans. Economics and Comput. 8 (1) (2020)
Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
Stochastic Submodular Cover with Limited Adaptivity. SODA (2019)
Sepehr Assadi, MohammadHossein Bateni, Vahab S. Mirrokni
Distributed Weighted Matching via Randomized Composable Coresets. ICML (2019)
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA (2019)
Sepehr Assadi, Aaron Bernstein
Towards a Unified Theory of Sparsification for Matching Problems. SOSA (2019)
Sepehr Assadi, Nikolai Karpov, Qin Zhang
Distributed and Streaming Linear Programming in Low Dimensions. PODS (2019)

Sepehr Assadi.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Sepehr Assadi