Soheil Behnezhad

101 papers A* 42A 3B 3Journal 50Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari
2026	J	`jnl`	Markov Chains with Rewinding. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2026	A*	`conf`	Vizing's Theorem in Deterministic Almost-Linear Time. SODA Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2025	A*	`conf`	Correlation Clustering Beyond the Pivot Algorithm. ICML Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2025	A*	`conf`	Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries. SODA Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
2025	J	`jnl`	Half-Approximating Maximum Dicut in the Streaming Setting. CoRR Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad Saneian
2025	A*	`conf`	Lower Bounds for Non-adaptive Local Computation Algorithms. FOCS Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2025	J	`jnl`	Lower Bounds for Non-adaptive Local Computation Algorithms. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2025	A*	`conf`	Massively Parallel Minimum Spanning Tree in General Metric Spaces. SODA Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong
2025	A*	`conf`	Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. SODA Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2025	A*	`conf`	Stochastic Matching via In-n-Out Local Computation Algorithms. STOC Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld
2025	A*	`conf`	Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. FOCS Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2025	J	`jnl`	Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. CoRR Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2025	J	`jnl`	Vizing's Theorem in Deterministic Almost-Linear Time. CoRR Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2025	A*	`conf`	Vizing's Theorem in Near-Linear Time. STOC Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2024	A*	`conf`	Approximating Maximum Matching Requires Almost Quadratic Time. STOC Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2024	J	`jnl`	Approximating Maximum Matching Requires Almost Quadratic Time. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2024	A*	`conf`	Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS. ICML Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
2024	J	`jnl`	Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS. CoRR Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
2024	J	`jnl`	Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries. CoRR Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
2024	J	`jnl`	Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2024	J	`jnl`	Fully Dynamic Matching and Ordered Ruzsa-Szemer\'edi Graphs. CoRR Soheil Behnezhad, Alma Ghafari
2024	A*	`conf`	Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs. FOCS Soheil Behnezhad, Alma Ghafari
2024	A*	`conf`	Fully Dynamic Matching: -Approximation in Polylog Update Time. SODA Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
2024	J	`jnl`	Massively Parallel Minimum Spanning Tree in General Metric Spaces. CoRR Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong
2024	J	`jnl`	Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. CoRR Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2024	J	`jnl`	Stochastic Matching via In-n-Out Local Computation Algorithms. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld
2024	A*	`conf`	Streaming Edge Coloring with Asymptotically Optimal Colors. ICALP Mohammad Saneian, Soheil Behnezhad
2024	A*	`conf`	Sublinear Algorithms for TSP via Path Covers. ICALP Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2024	J	`jnl`	Vizing's Theorem in Near-Linear Time. CoRR Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2023	A*	`conf`	Beating Greedy Matching in Sublinear Time. SODA Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2023	A*	`conf`	Dynamic Algorithms for Maximum Matching Size. SODA Soheil Behnezhad
2023	J	`jnl`	Exponentially Faster Massively Parallel Maximal Matching. J. ACM Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
2023	J	`jnl`	Fast and Simple Solutions of Blotto Games. Oper. Res. Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin
2023	J	`jnl`	Fully Dynamic Matching: (2-√2)-Approximation in Polylog Update Time. CoRR Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
2023	A*	`conf`	Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2023	J	`jnl`	Local Computation Algorithms for Maximum Matching: New Lower Bounds. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2023	A*	`conf`	On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
2023	A*	`conf`	Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. ICALP Amir Azarmehr, Soheil Behnezhad
2023	J	`jnl`	Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. CoRR Amir Azarmehr, Soheil Behnezhad
2023	A*	`conf`	Single-Pass Streaming Algorithms for Correlation Clustering. SODA Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2023	J	`jnl`	Streaming Edge Coloring with Asymptotically Optimal Colors. CoRR Soheil Behnezhad, Mohammad Saneian
2023	J	`jnl`	Sublinear Algorithms for TSP via Path Covers. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2023	A*	`conf`	Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. STOC Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2022	A*	`conf`	Almost 3-Approximate Correlation Clustering in Constant Rounds. FOCS Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2022	J	`jnl`	Almost 3-Approximate Correlation Clustering in Constant Rounds. CoRR Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan
2022	J	`jnl`	Beating Greedy Matching in Sublinear Time. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2022	J	`jnl`	Dynamic Algorithms for Maximum Matching Size. CoRR Soheil Behnezhad
2022	A*	`conf`	New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. SODA Soheil Behnezhad, Sanjeev Khanna
2022	J	`jnl`	New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. CoRR Soheil Behnezhad, Sanjeev Khanna
2022	J	`jnl`	On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
2022	A*	`conf`	Stochastic Vertex Cover with Few Queries. SODA Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
2022	J	`jnl`	Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2021	A*	`conf`	Beating Two-Thirds For Random-Order Streaming Matching. ICALP Sepehr Assadi, Soheil Behnezhad
2021	J	`jnl`	Beating Two-Thirds For Random-Order Streaming Matching. CoRR Sepehr Assadi, Soheil Behnezhad
2021	J	`jnl`	Improved Analysis of EDCS via Gallai-Edmonds Decomposition. CoRR Soheil Behnezhad
2021	J	`jnl`	Massively Parallel Computation via Remote Memory Access. ACM Trans. Parallel Comput. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
2021	—	`—`	Modern Large-Scale Algorithms for Classical Graph Problems. Soheil Behnezhad
2021	—	`conf`	On the Robust Communication Complexity of Bipartite Matching. APPROX-RANDOM Sepehr Assadi, Soheil Behnezhad
2021	J	`jnl`	Stochastic Vertex Cover with Few Queries. CoRR Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
2021	A*	`conf`	Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. FOCS Soheil Behnezhad
2021	J	`jnl`	Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. CoRR Soheil Behnezhad
2020	A*	`conf`	Fully Dynamic Matching: Beating 2-Approximation in Δ SODA Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni
2020	J	`jnl`	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice. CoRR Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
2020	J	`jnl`	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice. Proc. VLDB Endow. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
2020	J	`jnl`	Stochastic Matching with Few Queries: (1-ε) Approximation. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
2020	J	`jnl`	Stochastic Weighted Matching: $(1-ε)$ Approximation. CoRR Soheil Behnezhad, Mahsa Derakhshan
2020	A*	`conf`	Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation. FOCS Soheil Behnezhad, Mahsa Derakhshan
2020	A*	`conf`	Stochastic matching with few queries: (1-ε) approximation. STOC Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
2019	A	`conf`	Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring. DISC Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh
2019	A*	`conf`	Exponentially Faster Massively Parallel Maximal Matching. FOCS Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
2019	J	`jnl`	Exponentially Faster Massively Parallel Maximal Matching. CoRR Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
2019	J	`jnl`	Fully Dynamic Matching: Beating 2-Approximation in Δ CoRR Soheil Behnezhad, Jakub Lacki, Vahab S. Mirrokni
2019	A*	`conf`	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. FOCS Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
2019	J	`jnl`	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
2019	A*	`conf`	Massively Parallel Computation of Matching and MIS in Sparse Graphs. PODC Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, Jara Uitto
2019	B	`conf`	Massively Parallel Computation via Remote Memory Access. SPAA Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, Warren Schudy
2019	J	`jnl`	Massively Parallel Computation via Remote Memory Access. CoRR Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Warren Schudy, Vahab S. Mirrokni
2019	A*	`conf`	Near-Optimal Massively Parallel Graph Connectivity. FOCS Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni
2019	J	`jnl`	Near-Optimal Massively Parallel Graph Connectivity. CoRR Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni
2019	A*	`conf`	Optimal Strategies of Blotto Games: Beyond Convexity. EC Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin
2019	J	`jnl`	Optimal Strategies of Blotto Games: Beyond Convexity. CoRR Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Christos H. Papadimitriou, Saeed Seddighin
2019	B	`conf`	Stochastic Matching on Uniformly Sparse Graphs. SAGT Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
2019	A*	`conf`	Stochastic Matching with Few Queries: New Algorithms and Tools. SODA Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
2019	A	`conf`	Streaming and Massively Parallel Algorithms for Edge Coloring. ESA Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh
2018	A*	`conf`	Almost Optimal Stochastic Weighted Matching with Few Queries. EC Soheil Behnezhad, Nima Reyhani
2018	A*	`conf`	Brief Announcement: MapReduce Algorithms for Massive Trees. ICALP MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni
2018	J	`jnl`	Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
2018	A*	`conf`	From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. SODA Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark
2018	J	`jnl`	Massively Parallel Dynamic Programming on Trees. CoRR MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni
2018	J	`jnl`	Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Richard M. Karp
2018	A*	`conf`	Spatio-Temporal Games Beyond One Dimension. EC Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Saeed Seddighin
2018	J	`jnl`	Stochastic Matching with Few Queries: New Algorithms and Tools. CoRR Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani
2017	A	`conf`	A Pilot Deployment of an Online Tool for Large-Scale Virtual Auditing of Urban Accessibility. ASSETS Manaswi Saha, Kotaro Hara, Soheil Behnezhad, Anthony Li, Michael Saugstad, Hanuma Teja Maddali, Sage Chen, Jon E. Froehlich
2017	A*	`conf`	A Polynomial Time Algorithm for Spatio-Temporal Security Games. EC Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Aleksandrs Slivkins
2017	J	`jnl`	A Polynomial Time Algorithm for Spatio-Temporal Security Games. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Aleksandrs Slivkins
2017	—	`conf`	Affinity Clustering: Hierarchical Clustering at Scale. NIPS MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, Vahab S. Mirrokni
2017	J	`jnl`	Almost Optimal Stochastic Weighted Matching With Few Queries. CoRR Soheil Behnezhad, Nima Reyhani
2017	B	`conf`	Brief Announcement: Graph Matching in Massive Datasets. SPAA Soheil Behnezhad, Mahsa Derakhshan, Hossein Esfandiari, Elif Tan, Hadi Yami
2017	A*	`conf`	Faster and Simpler Algorithm for Optimal Strategies of Blotto Game. AAAI Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Saeed Seddighin
2016	J	`jnl`	Faster and Simpler Algorithm for Optimal Strategies of Blotto Game. CoRR Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Saeed Seddighin