Soheil Behnezhad

According to our database, Soheil Behnezhad authored at least 48 papers between 2017 and 2024.

Collaborative distances:

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

2024

Fully Dynamic Matching: -Approximation in Polylog Update Time.

Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani

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

2023

Exponentially Faster Massively Parallel Maximal Matching.

Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris

J. ACM, October, 2023

Fast and Simple Solutions of Blotto Games.

Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin

Oper. Res., March, 2023

Fully Dynamic Matching: (2-√2)-Approximation in Polylog Update Time.

Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani

CoRR, 2023

Streaming Edge Coloring with Asymptotically Optimal Colors.

Soheil Behnezhad, Mohammad Saneian

CoRR, 2023

Sublinear Algorithms for TSP via Path Covers.

Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi

CoRR, 2023

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching.

Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein

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

Beating Greedy Matching in Sublinear Time.

Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi

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

Single-Pass Streaming Algorithms for Correlation Clustering.

Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan

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

Dynamic Algorithms for Maximum Matching Size.

Soheil Behnezhad

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

Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation.

Amir Azarmehr, Soheil Behnezhad

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Local Computation Algorithms for Maximum Matching: New Lower Bounds.

Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein

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

2022

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS.

Soheil Behnezhad, Sanjeev Khanna

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

Stochastic Vertex Cover with Few Queries.

Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan

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

Almost 3-Approximate Correlation Clustering in Constant Rounds.

Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Modern Large-Scale Algorithms for Classical Graph Problems.

Soheil Behnezhad

PhD thesis, 2021

Massively Parallel Computation via Remote Memory Access.

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy

ACM Trans. Parallel Comput., 2021

Improved Analysis of EDCS via Gallai-Edmonds Decomposition.

Soheil Behnezhad

CoRR, 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

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover.

Soheil Behnezhad

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

On the Robust Communication Complexity of Bipartite Matching.

Sepehr Assadi, Soheil Behnezhad

Proceedings of the Approximation, 2021

2020

Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice.

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy

Proc. VLDB Endow., 2020

Stochastic Weighted Matching: $(1-ε)$ Approximation.

Soheil Behnezhad, Mahsa Derakhshan

CoRR, 2020

Stochastic matching with few queries: (1-ε) approximation.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi

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

Fully Dynamic Matching: Beating 2-Approximation in Δ^<i>ϵ</i> Update Time.

Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni

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

Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation.

Soheil Behnezhad, Mahsa Derakhshan

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

2019

Fully Dynamic Matching: Beating 2-Approximation in Δ^ε Update Time.

Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni

CoRR, 2019

Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Stochastic Matching with Few Queries: New Algorithms and Tools.

Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani

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

Stochastic Matching on Uniformly Sparse Graphs.

Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani

Proceedings of the Algorithmic Game Theory - 12th International Symposium, 2019

Massively Parallel Computation of Matching and MIS in Sparse Graphs.

Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto

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

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Near-Optimal Massively Parallel Graph Connectivity.

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Streaming and Massively Parallel Algorithms for Edge Coloring.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Optimal Strategies of Blotto Games: Beyond Convexity.

Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin

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

2018

Massively Parallel Dynamic Programming on Trees.

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni

CoRR, 2018

Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Richard M. Karp

CoRR, 2018

Brief Announcement: Semi-MapReduce Meets Congested Clique.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi

CoRR, 2018

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.

Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark

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

Almost Optimal Stochastic Weighted Matching with Few Queries.

Soheil Behnezhad, Nima Reyhani

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

Spatio-Temporal Games Beyond One Dimension.

Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Saeed Seddighin

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

Brief Announcement: MapReduce Algorithms for Massive Trees.

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Brief Announcement: Graph Matching in Massive Datasets.

Soheil Behnezhad, Mahsa Derakhshan, Hossein Esfandiari, Elif Tan, Hadi Yami

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

A Polynomial Time Algorithm for Spatio-Temporal Security Games.

Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Aleksandrs Slivkins

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

Affinity Clustering: Hierarchical Clustering at Scale.

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, Vahab S. Mirrokni

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

A Pilot Deployment of an Online Tool for Large-Scale Virtual Auditing of Urban Accessibility.

Manaswi Saha, Kotaro Hara, Soheil Behnezhad, Anthony Li, Michael Saugstad, Hanuma Teja Maddali, Sage Chen, Jon E. Froehlich

Proceedings of the 19th International ACM SIGACCESS Conference on Computers and Accessibility, 2017

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game.

Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017