Soheil Behnezhad
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
45
Venues
12
Active years
2017–2026
Best venue rank
A*
Where they publish
Papers
45 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | SODA | Vizing's Theorem in Deterministic Almost-Linear Time. | Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martn Costa, Shay Solomon, Tianyi Zhang |
| 2026 | STOC | Half-Approximating Maximum Dicut in the Streaming Setting. | Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad Saneian |
| 2025 | FOCS | Lower Bounds for Non-adaptive Local Computation Algorithms. | Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan |
| 2025 | FOCS | Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. | Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2025 | ICML | Correlation Clustering Beyond the Pivot Algorithm. | Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma |
| 2025 | SODA | Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. | Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan |
| 2025 | SODA | Massively Parallel Minimum Spanning Tree in General Metric Spaces. | Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong |
| 2025 | SODA | Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries. | Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim |
| 2025 | STOC | Vizing's Theorem in Near-Linear Time. | Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martn Costa, Shay Solomon, Tianyi Zhang |
| 2025 | STOC | Stochastic Matching via In-n-Out Local Computation Algorithms. | Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld |
| 2024 | FOCS | Fully Dynamic Matching and Ordered Ruzsa-Szemerdi Graphs. | Soheil Behnezhad, Alma Ghafari |
| 2024 | ICALP | Sublinear Algorithms for TSP via Path Covers. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2024 | ICALP | Streaming Edge Coloring with Asymptotically Optimal Colors. | Mohammad Saneian, Soheil Behnezhad |
| 2024 | ICML | Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS. | Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani |
| 2024 | SODA | Fully Dynamic Matching: -Approximation in Polylog Update Time. | Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani |
| 2024 | STOC | Approximating Maximum Matching Requires Almost Quadratic Time. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | FOCS | Local Computation Algorithms for Maximum Matching: New Lower Bounds. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | ICALP | Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. | Amir Azarmehr, Soheil Behnezhad |
| 2023 | SODA | Dynamic Algorithms for Maximum Matching Size. | Soheil Behnezhad |
| 2023 | SODA | Single-Pass Streaming Algorithms for Correlation Clustering. | Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan |
| 2023 | SODA | Beating Greedy Matching in Sublinear Time. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2023 | STOC | On Regularity Lemma and Barriers in Streaming and Dynamic Matching. | Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li |
| 2023 | STOC | Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2022 | FOCS | Almost 3-Approximate Correlation Clustering in Constant Rounds. | Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan |
| 2022 | SODA | Stochastic Vertex Cover with Few Queries. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan |
| 2022 | SODA | New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. | Soheil Behnezhad, Sanjeev Khanna |
| 2021 | FOCS | Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. | Soheil Behnezhad |
| 2021 | ICALP | Beating Two-Thirds For Random-Order Streaming Matching. | Sepehr Assadi, Soheil Behnezhad |
| 2020 | FOCS | Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation. | Soheil Behnezhad, Mahsa Derakhshan |
| 2020 | SODA | Fully Dynamic Matching: Beating 2-Approximation in Δ | Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni |
| 2020 | STOC | Stochastic matching with few queries: (1-ε) approximation. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi |
| 2019 | EC | Optimal Strategies of Blotto Games: Beyond Convexity. | Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin |
| 2019 | ESA | Streaming and Massively Parallel Algorithms for Edge Coloring. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh |
| 2019 | FOCS | Near-Optimal Massively Parallel Graph Connectivity. | Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni |
| 2019 | FOCS | Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan |
| 2019 | FOCS | Exponentially Faster Massively Parallel Maximal Matching. | Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris |
| 2019 | PODC | 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 |
| 2019 | SODA | Stochastic Matching with Few Queries: New Algorithms and Tools. | Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani |
| 2019 | SPAA | Massively Parallel Computation via Remote Memory Access. | Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy |
| 2019 | SAGT | Stochastic Matching on Uniformly Sparse Graphs. | Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani |
| 2018 | ICALP | Brief Announcement: MapReduce Algorithms for Massive Trees. | MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni |
| 2018 | SODA | 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 |
| 2017 | AAAI | Faster and Simpler Algorithm for Optimal Strategies of Blotto Game. | Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin |
| 2017 | ASSETS | 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 |
| 2017 | SPAA | Brief Announcement: Graph Matching in Massive Datasets. | Soheil Behnezhad, Mahsa Derakhshan, Hossein Esfandiari, Elif Tan, Hadi Yami |