Mahsa Derakhshan

Assistant Professor, Northeastern University

I am an assistant professor in the Khoury College of Computer Sciences at Northeastern University. Prior to that, I was a FODSI fellow at UC Berkeley and also a Postdoctoral Researcher at Princeton University in the Department of Computer Science. I received my Ph.D. in Computer Science from the University of Maryland.

Prospective Students: If you are a student with a strong background in theoretical computer science and mathematics, and if you are interested in working with me, apply to our Ph.D. program and mention my name in your application. Feel free to contact me directly if you have questions.

CV

Research Interests

I am broadly interested in the design and analysis of algorithms. Mainly, I study algorithms under uncertainty. A few sources of such uncertainty in my research are having stochastic data, limited access to information, and the presence of strategic behavior. I primarily study problems with applications to markets, such as matching markets and auctions.

Program Committees

ACM Conference on Economics and Computation (EC 2024)
ACM Symposium on Theory of Computing (STOC 2024)
ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
Innovations in Theoretical Computer Science (ITCS 2022)
European Symposium on Algorithms (ESA 2022)

Conference Publications

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling

M. Braverman, M. Derakhshan, T. Pollner, A. Saberi, D. Wajc

The 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)

Settling the Competition Complexity of Additive Buyers over Independent Items

M. Derakhshan, E. Ryu, M. Weinberg, E. Xue

The 25th ACM Conference on Economics and Computation (EC 2024)

Online Learning in Multi-unit Auctions

S. Brânzei, M. Derakhshan, N. Golrezaei, Y. Han

37th Conference on Neural Information Processing Systems (NeurIPS 2023)

Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation

M. Derakhshan, N. Durvasula, N. Haghtalab

55th Annual ACM Symposium on Theory of Computing (STOC 2023)

Beating (1−1/e)-Approximation for Weighted Stochastic Matching

M. Derakhshan, A. Frahadi

The 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark

M. Braverman, M. Derakhshan, A. Molina Lovett

The 23th ACM Conference on Economics and Computation (EC 2022)

Stochastic Vertex Cover with Few Queries

S. Behnezhad, A. Blum, M. Derakhshan

The 33th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)

Algorithms for Markets: Matching and Pricing

M. Derakhshan

Ph.D. Thesis, University of Maryland

Honorable mention for the ACM SIGecom Dissertation Award

Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions

M. Derakhshan, D. Pennock, A. Slivkins

The 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

Stochastic Weighted Matching: (1−ε) Approximation

S. Behnezhad, M. Derakhshan

61th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)

Product Ranking on Online Platforms

M. Derakhshan, N. Golrezaei, V. Manshadi, V. Mirrokni

The 21th ACM Conference on Economics and Computation (EC 2020)

Stochastic Matching with Few Queries: (1-ε) Approximation

S. Behnezhad, M. Derakhshan, M.T. Hajiaghayi

52nd Annual ACM Symposium on Theory of Computing (STOC 2020)

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

S. Behnezhad, M. Derakhshan, M.T. Hajiaghayi, C. Stein, M.Sudan

60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019)

LP-based Approximation for Personalized Reserve Prices

M. Derakhshan, N. Golrezaei, R. Paes Leme

The 20th ACM Conference on Economics and Computation (EC 2019)

Optimal Strategies of Blotto Games: Beyond Convexity

S. Behnezhad, A. Blum, M. Derakhshan, M.T. Hajiaghayi, C. Papadimitriou, S. Seddighin

The 20th ACM Conference on Economics and Computation (EC 2019)

Massively Parallel Computation of Matching and MIS in Sparse Graphs

S. Behnezhad, S. Brandt, M. Derakhshan, M. Fischer, M. Hajiaghayi, R. Karp, J. Uitto

The 38th ACM Symposium on Principles of Distributed Computing (PODC 2019)

Spatio-Temporal Games Beyond One Dimension

S. Behnezhad, M. Derakhshan, M.T. Hajiaghayi, S. Seddighin

The 19th ACM Conference on Economics and Computation (EC 2018)

Brief Announcement: MapReduce Algorithms on Massive Trees

M.H. Bateni , S. Behnezhad , M. Derakhshan, M.T. Hajiaghayi, V. Mirrokni

The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Winning Strategies of Blotto and Auditing Games

S. Behnezhad, A. Blum, M. Derakhshan, M.T. Hajiaghayi , M. Mahdian, C. Papadimitriou, R. Rivest, S. Seddighin, P. Stark

The 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)

Affinity Clustering: Hierarchical Clustering at Scale

M.H. Bateni , S. Behnezhad , M. Derakhshan, M.T. Hajiaghayi , R. Kiveris, S. Lattanzi , V. Mirrokni

The 31th Annual Conference on Neural Information Processing Systems (NIPS 2017)

A Polynomial Time Algorithm for Spatio-Temporal Games

S. Behnezhad , M. Derakhshan, M.T. Hajiaghayi , A. Slivkins

The 18th ACM Conference on Economics and Computation (EC 2017)

Brief Announcement: Graph Matching in Massive Datasets

S. Behnezhad , M. Derakhshan, H. Esfandiari , E. Tan, H. Yami

The 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017)

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

S. Behnezhad , S. Dehghani , M. Derakhshan, M.T. Hajiaghayi , S. Seddighin

The 31st AAAI Conference on Artificial Intelligence (AAAI 2017)

Journal Publications

LP-based Approximation for Personalized Reserve Prices

M. Derakhshan, N. Golrezaei , R. Paes Leme

Management Science (MS)—Special Issue on Data-Driven Prescriptive Analytics

Conference version appeared at ACM EC 2019

Product Ranking on Online Platforms

M. Derakhshan, N. Golrezaei, V. Manshadi, V. Mirrokni

Manegment Science (MS)

Conference version appeared at ACM EC 2020

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

S. Behnezhad , S. Dehghani , M. Derakhshan, M.T. Hajiaghayi , S. Seddighin

Operations Research (OR)

Conference version appeared at AAAI 2017