Selected Publications

R. Gao, M. Roghani, A. Rubinstein, A. Saberi, Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting, IEEE Symposium on Foundations of Computer Science (FOCS), 2024.

A. Hayderi, A. Saberi, E. Vitercik, A. Wikum, MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation, International Conference on Machine Learning (ICML), 2024.

A. Braun, T. Kesselheim, T. Pollner, A. Saberi, Approximating Optimum Online for Capacitated Resource Allocation, ACM Conference on Economics and Computation (EC), 2024.

S. Behnezhad, M. Roghani, A. Rubinstein, A. Saberi, Sublinear Algorithms for TSP via Path Covers, International Colloquium on Automata, Languages, and Programming (ICALP), 2024, 19:1-19:16.

S. Behnezhad, M. Roghani, A. Rubinstein, A. Saberi, Beating Greedy Matching in Sublinear Time, ACM-SIAM Symposium on Discrete Algorithms (SODA), 3900-3945, 2023.

Y. Alimohammadi, C. Borgs, A. Saberi, Locality of Random Digraphs on Expanders, The Annals of Probability, 51(4), 1249-1297, 2023.

Y. Alimohammadi, P. Diaconis, M. Roghani, A. Saberi, Sequential Importance Sampling for Estimating Expectations over the Space of Perfect Matchings, The Annals of Applied Probability, 33(2), 999-1033, 2023.

A. Asadpour, R. Niazadeh, A. Saberi, A. Shameli, Sequential Submodular Maximization and Applications to Ranking an Assortment of Products, Operations Research, 71(4), 1154-1170, 2023. Conference version appeared in ACM Conference on Economics and Computation (EC) 2002.

I. Ashlagi, M. Burq, C. Dutta, P. Jaillet, A. Saberi, C. Sholley, Edge-Weighted Online Windowed Matching, Mathematics of Operations Research 48(2): 999-1016. 2023.

Y. Feng, R. Niazadeh, A. Saberi, Two-Stage Stochastic Matching and Pricing with Applications to Ride Hailing, Operations Research, 2023.

S. Behnezhad, M. Roghani, A. Rubinstein, A. Saberi, Beating Greedy Matching in Sublinear Time, ACM-SIAM Symposium on Discrete Algorithms (SODA), 3900-3945, 2023.

T. Pollner, M. Roghani, A. Saberi, D. Wajc, Improved Online Contention Resolution for Matchings and Applications to the Gig Economy, ACM Conference on Economics and Computation (EC), 321-322, 2022.

Y. Alimohammadi, C. Borgs, A. Saberi, Algorithms Using Local Graph Features to Predict Epidemics, ACM-SIAM Symposium on Discrete Algorithms (SODA), 3430-3451, 2022.

K. Kessel, A. Shameli, A. Saberi, D. Wajc, The Stationary Prophet Inequality Problem, ACM Conference on Economics and Computation (EC), 243-244, 2022.

Y. Feng, R. Niazadeh, A. Saberi, Near-Optimal Bayesian Online Assortment of Reusable Resources, ACM Conference on Economics and Computation (EC), 964-965, 2022.

M. Pavone, A. Saberi, M. Schiffer, M. W. Tsao, Online Hypergraph Matching with Delays, Operations Research, 70(4), 2194-2212, 2022.

Y. Alimohammadi, A. Saberi, M. Akbarpour, S. Li, The Value of Excess Supply in Spatial Matching Markets, ACM conference on Economics and Computation (EC 2022).

K. Kessel, A. Shameli, A. Saberi, D. Wajc, The Stationary Prophet Inequality Problem, ACM conference on Economics and Computation (EC 2022).

Y. Alimohammadi, C. Borgs, A. Saberi, Algorithms Using Local Graph Features to Predict Epidemics, ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).

M. Roghani, A. Saberi, D. Wajc, Beating the Folklore Algorithm for Dynamic Matching, Innovations in Theoretical Computer Science (ITCS 2022).

A. Saberi, D. Wajc, The Greedy Algorithm is not optimal for On-Line Edge Coloring, International Colloquium on Automata, Languages and Programming (ICALP 2021).

M. Y. Jeloudar, I. Lo, T. Pollner, A. Saberi, Decentralized Matching in Probabilistic Environments, ACM conference on Economics and Computation (EC 2021).

C. Papadimitriou, T. Pollner, A. Saberi, D. Wajc, Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities, ACM conference on Economics and Computation (EC 2021).

I. Ashlagi, M. Braverman, A. Saberi, C. Thomas, and G. Zhao, Tiered Random Matching Markets: Rank Is Proportional to Popularity, Innovations in Theoretical Computer Science (ITCS 2021).

N. Anari, N. Hu, A. Saberi, and A. Schild, Sampling Arborescences in Parallel, Innovations in Theoretical Computer Science (ITCS 2021).

Y. Feng, R. Niazadeh, A. Saberi, Two-stage Matching and Pricing with Applications to Ride Hailing, ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).

I. Ashlagi, J. Leshno, P. Qian, A. Saberi Queue Lengths as Constantly Adapting Prices: Allocative Efficiency Under Random Dynamics, ACM Conference on Economics and Computation (EC 2020).

I. Ashlagi, A. Saberi, A. Shameli, Assignment Mechanisms under Distributional Constraints, Operations Research (2020). Conference version in ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).

M. Akbarpour, S. Malladi, and A. Saberi, Diffusion, Seeding, and the Value of Network Information, Revise and Resubmit, American Economic Review (AER). Conference version in the ACM conference on Economics and Computation (EC 2018).

A. Ahmadi, H. Nazerzadeh, A. Saberi, N. Skochdopole and K. Sweeney, Competition in Ride-Hailing Markets, Conference on Web and Internet Economics (WINE 2019).

N. Anari, R. Niazadeh, A. Saberi, A. Shameli, Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection, ACM conference on Economics and Computation (EC 2019).

A. Ahmadi, A. Jambulapati, A. Saberi, A. Sidford, Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications, ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).

R. Niazadeh, A. Saberi and A. Shameli, Prophet Inequalities vs. Approximating Optimum Online, Conference on Web and Internet Economics (WINE 2018).

N. Anari, S. Gharan, A. Saberi, and N. Srivastava, Approximating the Largest Root and Applications to Interlacing Families, ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

R. Vaish, S. Goel, and A. Saberi, Creating Crowdsourced Research Talks at Scale, WWW 2018. Preliminary version appeared in Learning @ Scale 2017. See also the project site and the video clip.

M. Bayati, A. Montanari, and A. Saberi, Generating Random Graphs without Short Cycles, Operations Research (2018).

M. Akbarpour, A. Saberi and A. Shameli, Information aggregation in overlapping generations and the emergence of highly informed individuals, WINE 2017 (best paper award).

N. Anari, S. Gharan, L. Gurvits, and A. Saberi, Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices, FOCS 2017.

A. Shameli, T. Althoff, A. Saberi, and J. Leskovec, How Gamification Affects Physical Activity: Large-scale Analysis of Walking Challenges in a Mobile Application, WWW 2017.

A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, Operations Research 65:4, 1043-1061 (2017). (The conference version received the best paper award in SODA 2010.)

N. Anari, S. Gharan, A. Saberi, and M. Singh, Nash Social Welfare, Matrix Permanent, and Stable Polynomials, ITCS 2017 (accepted with distinction).

L. Fleischer, R. Garg, S. Kapoor, R., and A. Saberi, A Simple and Efficient Algorithm for Computing Market Equilibria, ACM Transactions on Algorithms 12(3): 34:1-34:15 (2016).

A. Kim, V. Liaghat, J. Qin, and A. Saberi, Online Energy Storage Management: an Algorithmic Approach, APPROX-RANDOM 2016.

G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi, Approximation Algorithms for Computing Maximin Share Allocations, ICALP 2015.

N. Berger, C. Borgs, J. T. Chayes, and A. Saberi, Asymptotic Behavior and Distributional Limits of Preferential Attachment Graphs, Annals of Probability, Volume 42, Number 1 (2014).

H. Nazerzadeh, A. Saberi, and R. Vohra, Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising, Operations Research 61(1): 98-111 (2013).

V. Manshadi, S. Oveis Gharan, and A. Saberi, Online Stochastic Matching: Online Actions Based on Offline Statistics, Mathematics of Operations Research 37(4): 559-573 (2012).

S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, FOCS 2011 (best paper award).

A. Montanari, A. Saberi, The Spread of Innovations in Social Networks, in Proceedings of the National Academy of Sciences. See also the supplementary information, the conference version which appeared in FOCS 2009, and a short excerpt in ACM SIGecom exchanges.

V. Manshadi, S. Oveis Gharan, A. Saberi, Online Stochastic Matching: Online Actions Based on Offline Statistics, SODA 2011.

A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, Adwords and Generalized On-line Matching , Journal of the ACM (2007). Conference version appeared in IEEE Symposium on Foundations of Computer Science (2005). A SIAM News article by Sara Robinson on this work.

Courses

Over the years, I have taught several iterations of the following courses:

Large Networks and Graph Limits
Matching Theory
Approximation Algorithms
Combinatorial Optimization (MS&E 212)
Spectral Graph Theory and Algorithmic Applications
Introduction to Optimization (MS&E 111)
Discrete Mathematics and Algorithms (CME 305)
Computation of Equilibria

Graduate Students

Mohsen Bayati (2007), Professor, Graduate School of Business, Stanford University.
Hamid Nazerzadeh (2009), Associate Professor, University of Southern California. Now Director of Engineering and Applied Sciences, Uber.
Arash Asadpour (2010), Assistant professor, New York University. Now Associate Professor at CUNY.
Simla Ceyhan (2011), Director of Data Science at Wish.
Vahideh Manshadi (2011), Professor, Yale School of Management.
Shayan Oveis Gharan (2013), Professor, Department of Computer Science and Engineering, University of Washington.
Farnaz Ronaghi (2016), Chief Technology Officer, NovoEd.
Anthony Kim (2018), Assistant Professor of Decision Sciences at Sungkyunkwan University.
Nolan Skochdopole (2019), Researcher at Uber.
Amirmahdi Ahmadinejad (co-advised with Aaron Sidford) (2019), Researcher at Amazon.
Ali Shameli (2020), Postdoc at MIT.
Kristen Kessel (2021), Quantitative Researcher at a Hedge Fund.
Yeganeh Alimohammadi (2024), President's Postdoctoral Fellow at UC Berkeley (2024-2025). Assistant Professor, University of Southern California, Marshall School of Business (Starting in 2025).
Tristan Pollner, Department of Management Science and Engineering, Stanford University.
Mohammad Roghani, Department of Management Science and Engineering, Stanford University.

Postdoctoral Researchers

Vahid Liaghat (2015-2016), Researcher, Facebook.
Rajan Vaish (2016-2017), with Sharad Goel, CEO at Easel AI, Inc.
Nima Anari (2016-2017), Assistant Professor, Computer Science Department, Stanford University.
Rad Niazadeh (2018-2020), Assistant Professor, Chicago Booth School of Business.
David Wajc (2020-2022), Visiting Researcher, Google.
Soheil Behnezhad (2021-2022), Assistant Professor, Computer Science Department, Northeastern University.
Sophie Yu (2023-2024), Assistant Professor, Wharton School of the University of Pennsylvania.

Contact Information

Huang Engineering Center, Office 309
475 Via Ortega
Stanford, CA 94305-4121
Office: (650) 724-2052
Email: saberi@stanford.edu

Assistant: Jackie Nguyen
Phone: (650) 723-4173
Fax: (650) 723-1614
Email: jackie.nguyen@stanford.edu