Sepehr Assadi

CoRR, 2024

Faster Vizing and Near-Vizing Edge Coloring Algorithms.

[BibT_eX]

[DOI]

CoRR, 2024

O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

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

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

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

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Recent Advances in Multi-Pass Graph Streaming Lower Bounds.

[BibT_eX]

[DOI]

SIGACT News, September, 2023

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

[BibT_eX]

[DOI]

Pankaj Kumar

Parth Mittal

TheoretiCS, 2023

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

[BibT_eX]

[DOI]

Gillat Kol

Zhijun Zhang

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Janani Sundaresan

CoRR, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

Janani Sundaresan

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

On Regularity Lemma and Barriers in Streaming and Dynamic Matching.

[BibT_eX]

[DOI]

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

Tight Bounds for Vertex Connectivity in Dynamic Streams.

[BibT_eX]

[DOI]

Vihan Shah

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Tight Bounds for Monotone Minimal Perfect Hashing.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Vihan Shah

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.

[BibT_eX]

[DOI]

Zachary Langley

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

Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Janani Sundaresan

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

On Constructing Spanners from Random Gaussian Projections.

[BibT_eX]

[DOI]

Michael Kapralov

Huacheng Yu

Proceedings of the Approximation, 2023

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Rounds vs Communication Tradeoffs for Maximal Independent Sets.

[BibT_eX]

[DOI]

Gillat Kol

Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Ariel Schvartzman

CoRR, 2022

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Chaoji Zuo

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Decremental Matching in General Graphs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Hoai-An Nguyen

Proceedings of the Approximation, 2022

2021

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Ruling Sets in Random Order and Adversarial Streams.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Aditi Dudeja

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

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

[BibT_eX]

[DOI]

Thomas Kesselheim

Sahil Singla

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

Beating Two-Thirds For Random-Order Streaming Matching.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Shay Solomon

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

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

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

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

On the Robust Communication Complexity of Bipartite Matching.

[BibT_eX]

[DOI]

Soheil Behnezhad

Proceedings of the Approximation, 2021

2020

Combinatorial Auctions Do Need Modest Interaction.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2020

Improved truthful mechanisms for combinatorial auctions with submodular bidders.

[BibT_eX]

[DOI]

Sahil Singla

SIGecom Exch., 2020

Improved Bounds for Distributed Load Balancing.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Palette Sparsification Beyond (Δ+1) Vertex Coloring.

[BibT_eX]

[DOI]

Noga Alon

Proceedings of the Approximation, 2020

2019

The Stochastic Matching Problem with (Very) Few Queries.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2019

Polynomial pass lower bounds for graph streaming algorithms.

[BibT_eX]

[DOI]

Yu Chen

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

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

[BibT_eX]

[DOI]

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

Sublinear Algorithms for (Δ + 1) Vertex Coloring.

[BibT_eX]

[DOI]

Yu Chen

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

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

[BibT_eX]

[DOI]

MohammadHossein Bateni

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.

[BibT_eX]

[DOI]

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

Stochastic Submodular Cover with Limited Adaptivity.

[BibT_eX]

[DOI]

Arpit Agarwal

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

Distributed and Streaming Linear Programming in Low Dimensions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Xiaorui Sun

Omri Weinstein

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

Secretary Ranking with Minimal Inversions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Michael Kapralov

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

Distributed Weighted Matching via Randomized Composable Coresets.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Shay Solomon

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

2018

Fully dynamic maximal independent set with sublinear update time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2017

Fast Convergence in the Double Oral Auction.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2017

On the rectangle escape problem.

[BibT_eX]

[DOI]

AmirMahdi Ahmadinejad

Ehsan Emamjomeh-Zadeh

Sadra Yazdanbod

Hamid Zarrabi-Zadeh

Theor. Comput. Sci., 2017

SPAA 2017 Review.

[BibT_eX]

[DOI]

SIGACT News, 2017

Simple Round Compression for Parallel Vertex Cover.

[BibT_eX]

[DOI]

CoRR, 2017

Randomized Composable Coresets for Matching and Vertex Cover.

[BibT_eX]

[DOI]

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

On Estimating Maximum Matching Size in Graph Streams.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Morteza Mohajjel Kafshdooz

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Mohammadkazem Taram

Alireza Ejlali

ACM Trans. Archit. Code Optim., 2016

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

[BibT_eX]

[DOI]

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

Algorithms for Provisioning Queries and Analytics.

[BibT_eX]

[DOI]

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

2015

Tight Bounds for Linear Sketches of Approximate Matchings.

[BibT_eX]

[DOI]

CoRR, 2015

Online Assignment of Heterogeneous Tasks in Crowdsourcing Markets.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2014

The Minimum Vulnerability Problem.

[BibT_eX]

[DOI]

Ehsan Emamjomeh-Zadeh

Ashkan Norouzi-Fard

Sadra Yazdanbod

Hamid Zarrabi-Zadeh

Algorithmica, 2014

2013

On the Rectangle Escape Problem.

[BibT_eX]

[DOI]