Soheil Behnezhad

Soheil Behnezhad is an Assistant Professor in the Department of Computer Science at Khoury College of Computer Sciences, Northeastern University. He previously served as a Motwani Postdoctoral Fellow at Stanford University and received his PhD from the University of Maryland (UMD) and BSc from Sharif University.

Research Interests: His work centers on theoretical computer science, particularly the design and analysis of algorithms for large-scale data. Key areas include sublinear-time algorithms, dynamic algorithms, streaming algorithms, parallel computation (MPC), and graph sparsification, with a strong emphasis on matching, coloring, and clustering problems.

Recent Trends in Publications: His recent publications (2023–2025) highlight groundbreaking work in dynamic and sublinear algorithms. He has made significant advances in maximum matching, edge coloring, and correlation clustering, often providing tight bounds or breaking longstanding approximation barriers. His work connects theoretical models with combinatorial structures such as Ruzsa-Szemerédi graphs and explores practical implications in massive data settings.

Scientific Awards:

• NSF CAREER Award
• Google Research Award
• Best Paper Award at STOC'25
• Best Paper Award at SODA'23
• Charles A. Caramello Distinguished Dissertation Award
• Larry S. Davis Doctoral Dissertation Award
• Multiple invitations to TALG and HALG

Advising and Grants: He advises multiple PhD students including Amir Azarmehr, Mohammad Saneian, and Alma Ghafari. His research is supported by an NSF CAREER Award and a Google Research Award, reflecting both federal and industry recognition of his impactful work.

Labs and Teams: He co-organizes the Graph Simplification reading group with Ronitt Rubinfeld and Madhu Sudan and is a key member of the Theory Group at Northeastern University, fostering a collaborative environment for theoretical research.