Amin Saberi Professor MS&E | OR | TCS | SOAL | ICME Stanford University A short bio

Selected Publications

Y. Alimohammadi, P. Diaconis, M. Roghani, A. Saberi, ,Sequential Importance Sampling for Estimating Expectations over the Space of Perfect Matchings, to appear in the Annals of Applied Probability, 2022.

M. Pavone, A. Saberi, M. Schiffer, M. Tsao, Online Hypergraph Matching with Delays, to appear in the Operations Research 2022.

I. Ashlagi, M. Burq, C. Dutta, P. Jaillet, A. Saberi, and C. Sholley, Maximum Weight Online Matching with Deadlines, to appear in the Mathematics of Operations Research (2022).

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 2022).

A. Asadpour, R. Niazadeh, A. Saberi, A. Shameli, Sequential Submodular Maximization and Applications to Ranking an Assortment of Products , ACM conference on Economics and Computation (EC 2022).

Y. Feng, R. Niazadeh, A. Saberi, Near-Optimal Bayesian Online Assortment of Reusable Resources, ACM conference on Economics and Computation (EC 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).

Y. Alimohammadi, C. Borgs, A. Saberi, Locality of Random Digraphs on Expanders, under review.

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).

Y. Feng, R. Niazadeh, A. Saberi, Linear Programming Based Online Policies for Real-Time Assortment of Reusable Resources, preprint (2019).

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

Spring 2019, 2022: Matching Theory (MS&E 319)
Winter 07, Spring 2011, Fall 2016, Fall 2022: Approximation Algorithms (MS&E 319)
Winter 2013-2022: Combinatorial Optimization (MS&E 212)
Spring 2016: Spectral Graph Theory and Algorithmic Applications (MS&E 337)
Autumn 09, Spring 06, Spring 14, Winter 15, Winter 18, Winter 19: Introduction to Optimization (MS&E111)
Winter 05-11: Discrete Mathematics and Algorithms (CME 305)
Autumn 05, Autumn 07, Autumn 2010: Information Networks (MS&E 337)
Spring 08: Computation of Equilibria (MS&E 334)

Graduate Students

Mohsen Bayati, graduated in 2007. Associate professor, Graduate School of Business, Stanford University.
Hamid Nazerzadeh, graduated in 2009, Associate Professor, University of Southern California.
Arash Asadpour, graduated in 2010. Assistant professor, New York University. Now associate professor at CUNY.
Simla Ceyhan, graduated in 2011, Director of Data Science at Wish.
Vahideh Manshadi, graduated in 2011. Associate Professor, Yale School of Management.
Shayan Oveis Gharan, graduated in 2013. Associate Professor, Department of Computer Science and Engineering, University of Washington.
Farnaz Ronaghi, graduated in 2016. Chief Technology Officer, NovoEd.
Anthony Kim, graduated in 2018. Postdoc at Columbia Business School.
Ali Shameli, graduated in 2020. Postdoc at MIT.
Nolan Skochdopole, graduated in 2019. Researcher at Uber.
Amirmahdi Ahmadinejad (co-advised with Aaron Sidford), graduated in 2019. Researcher at Amazon.
Kristen Kessel, PhD candidate, Institute for Computational and Mathematical Engineering, Stanford University.
Yeganeh Alimohammadi, Department of Management Science and Engineering, Stanford University.

Postdoctoral researchers

Soheil Behnezhad, 2021-2022. Assistant Professor at Northeastern Univesity.
David Wajc, 2020-2022. Visiting Researcher at Google.
Rad Niazadeh, 2018-2020. Assistant Professor, Chicago Booth School of Business (starting in Fall 2020).
Nima Anari, 2016-2017. Assistant Professor, Computer Science Department, Stanford University.
Rajan Vaish, with Sharad Goel, 2016-2017, now at Snap Inc.
Vahid Liaghat, 2015-2016, now at Facebook.

Academic Affiliations

The Operations Research group
Theoretical Computer Science
The Social Algorithms Lab. Also see the RAIN seminar
The Institute for Computational and Mathematical Engineering

Contact Information

Huang Engineering Center, Office 309 475 Via Ortega Stanford, CA 94305-4121 Office: (650) 724-2052 Cell: (650) 704-7857

Assistant: Jenny Lam Phone: (650) 723-4173 Fax: (650) 723-1614 Email: lamjenny@stanford.edu