Soheil Behnezhad
Assistant Professor
Research interests
- Graph algorithms
- Parallel algorithms
- Sublinear algorithms
- Dynamic algorithms
- Streaming algorithms
Education
- PhD in Computer Science, University of Maryland
- BSc in Software Engineering, Sharif University of Technology — Iran
Biography
Soheil Behnezhad is an associate professor in the Khoury College of Computer Sciences at Northeastern University, based in Boston.
Before joining Northeastern, he was a Motwani postdoc at Stanford. He is broadly interested in theoretical computer science. Much of his work focuses on graph algorithms and the theoretical foundations of big data algorithms. This includes sublinear time algorithms, parallel algorithms, streaming algorithms, dynamic algorithms, and graph sparsifiers.
Behnezhad is the author of many papers in leading conferences in theoretical computer science for which he has won a number of awards, including a STOC 2025 best paper award, a SODA 2023 best paper award, an NSF CAREER award, a Google Research award, and a best thesis award at UMD, among others.
Recent publications
-
Vizing’s Theorem in Near-Linear Time
Citation: Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang . (2025). Vizing's Theorem in Near-Linear Time STOC, 24-35. https://doi.org/10.1145/3717823.3718265 -
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Citation: Sepehr Assadi, Soheil Behnezhad, Christian Konrad , Kheeran K. Naidu, Janani Sundaresan. (2025). Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams SODA, 864-904. https://doi.org/10.1137/1.9781611978322.25 -
Massively Parallel Minimum Spanning Tree in General Metric Spaces
Citation: Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong. (2025). Massively Parallel Minimum Spanning Tree in General Metric Spaces SODA, 143-174. https://doi.org/10.1137/1.9781611978322.5 -
Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries
Citation: Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim. (2025). Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries SODA, 4983-5026. https://doi.org/10.1137/1.9781611978322.169 -
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Citation: Soheil Behnezhad, Alma Ghafari. (2024). Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs FOCS, 314-327. https://doi.org/10.1109/FOCS61266.2024.00027 -
Approximating Maximum Matching Requires Almost Quadratic Time
Citation: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein. (2024). Approximating Maximum Matching Requires Almost Quadratic Time STOC, 444-454. https://doi.org/10.1145/3618260.3649785 -
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Citation: Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani. (2024). Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS ICML. https://openreview.net/forum?id=EDEISRmi6X -
Fully Dynamic Matching: -Approximation in Polylog Update Time
Citation: Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani. (2024). Fully Dynamic Matching: -Approximation in Polylog Update Time SODA, 3040-3061. https://doi.org/10.1137/1.9781611977912.109 -
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Citation: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein. (2023). Local Computation Algorithms for Maximum Matching: New Lower Bounds FOCS, 2322-2335. https://doi.org/10.1109/FOCS57990.2023.00143 -
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Citation: Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li. (2023). On Regularity Lemma and Barriers in Streaming and Dynamic Matching STOC, 131-144. https://doi.org/10.1145/3564246.3585110 -
Beating Greedy Matching in Sublinear Time
Citation: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi. (2023). Beating Greedy Matching in Sublinear Time SODA, 3900-3945. https://doi.org/10.1137/1.9781611977554.ch151 -
Dynamic Algorithms for Maximum Matching Size
Citation: Soheil Behnezhad. (2023). Dynamic Algorithms for Maximum Matching Size SODA, 129-162. https://doi.org/10.1137/1.9781611977554.ch6 -
Single-Pass Streaming Algorithms for Correlation Clustering
Citation: Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan. (2023). Single-Pass Streaming Algorithms for Correlation Clustering SODA, 819-849. https://doi.org/10.1137/1.9781611977554.ch33 -
Almost 3-Approximate Correlation Clustering in Constant Rounds
Citation: Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan. (2022). Almost 3-Approximate Correlation Clustering in Constant Rounds FOCS, 720-731. https://doi.org/10.1109/FOCS54457.2022.00074 -
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
Citation: Soheil Behnezhad, Sanjeev Khanna. (2022). New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS SODA, 3529-3566. https://doi.org/10.1137/1.9781611977073.140 -
Stochastic Vertex Cover with Few Queries
Citation: Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan. (2022). Stochastic Vertex Cover with Few Queries SODA, 1808-1846. https://doi.org/10.1137/1.9781611977073.73 -
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Citation: Soheil Behnezhad. (2021). Time-Optimal Sublinear Algorithms for Matching and Vertex Cover FOCS, 873-884. https://doi.org/10.1109/FOCS52979.2021.00089
