Soheil Behnezhad

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 80

Top Topics

Massive Datasets

Massively Parallel

Correlation Clustering

Maximum Matching

Top Venues

Publications

Soheil Behnezhad, Alma Ghafari
Fully Dynamic Matching and Ordered Ruzsa-Szemer\'edi Graphs. CoRR (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)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Approximating Maximum Matching Requires Almost Quadratic Time. CoRR (2024)
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR (2024)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Sublinear Algorithms for TSP via Path Covers. ICALP (2024)
Mohammad Saneian, Soheil Behnezhad
Streaming Edge Coloring with Asymptotically Optimal Colors. ICALP (2024)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Approximating Maximum Matching Requires Almost Quadratic Time. STOC (2024)
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS. CoRR (2024)
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Fully Dynamic Matching: -Approximation in Polylog Update Time. SODA (2024)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. J. ACM 70 (5) (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. STOC (2023)
Soheil Behnezhad
Dynamic Algorithms for Maximum Matching Size. SODA (2023)
Amir Azarmehr, Soheil Behnezhad
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Sublinear Algorithms for TSP via Path Covers. CoRR (2023)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Single-Pass Streaming Algorithms for Correlation Clustering. SODA (2023)
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Fully Dynamic Matching: (2-√2)-Approximation in Polylog Update Time. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Beating Greedy Matching in Sublinear Time. SODA (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Local Computation Algorithms for Maximum Matching: New Lower Bounds. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS (2023)
Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin
Fast and Simple Solutions of Blotto Games. Oper. Res. 71 (2) (2023)
Amir Azarmehr, Soheil Behnezhad
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. ICALP (2023)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC (2023)
Soheil Behnezhad, Mohammad Saneian
Streaming Edge Coloring with Asymptotically Optimal Colors. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Beating Greedy Matching in Sublinear Time. CoRR (2022)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS (2022)
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
Stochastic Vertex Cover with Few Queries. SODA (2022)
Soheil Behnezhad, Sanjeev Khanna
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. SODA (2022)
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR (2022)
Soheil Behnezhad, Sanjeev Khanna
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. CoRR (2022)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. CoRR (2022)
Soheil Behnezhad
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. FOCS (2022)
Soheil Behnezhad
Dynamic Algorithms for Maximum Matching Size. CoRR (2022)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR (2022)
Sepehr Assadi, Soheil Behnezhad
On the Robust Communication Complexity of Bipartite Matching. APPROX-RANDOM (2021)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
Massively Parallel Computation via Remote Memory Access. ACM Trans. Parallel Comput. 8 (3) (2021)
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
Stochastic Vertex Cover with Few Queries. CoRR (2021)
Soheil Behnezhad
Improved Analysis of EDCS via Gallai-Edmonds Decomposition. CoRR (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)
Soheil Behnezhad
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. FOCS (2021)
Soheil Behnezhad
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. CoRR (2021)
Soheil Behnezhad, Mahsa Derakhshan
Stochastic Weighted Matching: $(1-ε)$ Approximation. CoRR (2020)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice. CoRR (2020)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice. Proc. VLDB Endow. 13 (13) (2020)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Stochastic matching with few queries: (1-ε) approximation. STOC (2020)
Soheil Behnezhad, Mahsa Derakhshan
Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation. FOCS (2020)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Stochastic Matching with Few Queries: (1-ε) Approximation. CoRR (2020)
Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni
Update Time. SODA (2020)
Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
Stochastic Matching with Few Queries: New Algorithms and Tools. SODA (2019)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Warren Schudy, Vahab S. Mirrokni
Massively Parallel Computation via Remote Memory Access. CoRR (2019)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni
Near-Optimal Massively Parallel Graph Connectivity. FOCS (2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. CoRR (2019)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni
Near-Optimal Massively Parallel Graph Connectivity. CoRR (2019)
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
Massively Parallel Computation via Remote Memory Access. SPAA (2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. FOCS (2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh
Streaming and Massively Parallel Algorithms for Edge Coloring. ESA (2019)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. CoRR (2019)
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin
Optimal Strategies of Blotto Games: Beyond Convexity. CoRR (2019)
Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni
Update Time. CoRR (2019)
Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
Stochastic Matching on Uniformly Sparse Graphs. SAGT (2019)
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto
Massively Parallel Computation of Matching and MIS in Sparse Graphs. PODC (2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh
Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring. DISC (2019)
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin
Optimal Strategies of Blotto Games: Beyond Convexity. EC (2019)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. FOCS (2019)
MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni
Brief Announcement: MapReduce Algorithms for Massive Trees. ICALP (2018)
Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
Stochastic Matching with Few Queries: New Algorithms and Tools. CoRR (2018)
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. SODA (2018)
Soheil Behnezhad, Nima Reyhani
Almost Optimal Stochastic Weighted Matching with Few Queries. EC (2018)
MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni
Massively Parallel Dynamic Programming on Trees. CoRR (2018)
Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Saeed Seddighin
Spatio-Temporal Games Beyond One Dimension. EC (2018)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Richard M. Karp
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching. CoRR (2018)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR (2018)
Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin
Faster and Simpler Algorithm for Optimal Strategies of Blotto Game. AAAI (2017)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Aleksandrs Slivkins
A Polynomial Time Algorithm for Spatio-Temporal Security Games. CoRR (2017)
MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, Vahab S. Mirrokni
Affinity Clustering: Hierarchical Clustering at Scale. NIPS (2017)
Soheil Behnezhad, Mahsa Derakhshan, Hossein Esfandiari, Elif Tan, Hadi Yami
Brief Announcement: Graph Matching in Massive Datasets. SPAA (2017)
Soheil Behnezhad, Nima Reyhani
Almost Optimal Stochastic Weighted Matching With Few Queries. CoRR (2017)
Manaswi Saha, Kotaro Hara, Soheil Behnezhad, Anthony Li, Michael Saugstad, Hanuma Teja Maddali, Sage Chen, Jon E. Froehlich
A Pilot Deployment of an Online Tool for Large-Scale Virtual Auditing of Urban Accessibility. ASSETS (2017)
Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Aleksandrs Slivkins
A Polynomial Time Algorithm for Spatio-Temporal Security Games. EC (2017)
Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Saeed Seddighin
Faster and Simpler Algorithm for Optimal Strategies of Blotto Game. CoRR (2016)