Bio


Amin Saberi is Professor of Management Science and Engineering at Stanford University. He received his B.Sc. from Sharif University of Technology and his Ph.D. from Georgia Institute of Technology in Computer Science. His research interests include algorithms, design and analysis of social networks, and applications. He is a recipient of the Terman Fellowship, Alfred Sloan Fellowship and several best paper awards.
Amin was the founding CEO and chairman of NovoEd Inc., a social learning environment designed in his research lab and used by universities such as Stanford as well as non-profit and for-profit institutions for offering courses to hundreds of thousands of learners around the world.

Academic Appointments


Professional Education


  • BS, Sharif Institute of Technology, Tehran, Iran, Computer Science (2000)
  • PhD, Georgia Institute of Technology, Computer Science (2004)

2021-22 Courses


Stanford Advisees


All Publications


  • Assignment Mechanisms Under Distributional Constraints OPERATIONS RESEARCH Ashlagi, I., Saberi, A., Shameli, A. 2020; 68 (2): 467–79
  • Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection Anari, N., Niazadeh, R., Saberi, A., Shameli, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2019: 91–92
  • Competition in Ride-Hailing Markets Ahmadinejad, A., Nazerzadeh, H., Saberi, A., Skochdopole, N., Sweeney, K., Caragiannis, Mirrokni, Nikolova, E. SPRINGER INTERNATIONAL PUBLISHING AG. 2019: 333
  • Edge Weighted Online Windowed Matching Ashlagi, I., Burq, M., Dutta, C., Jaillet, P., Saberi, A., Sholley, C., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2019: 729–42
  • Generating Random Networks Without Short Cycles OPERATIONS RESEARCH Bayati, M., Montanari, A., Saberi, A. 2018; 66 (5): 1227–46
  • Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons Anari, N., Daskalakis, C., Maass, W., Papadimitriou, C. H., Saberi, A., Vempala, S., Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018
  • Approximating the Largest Root and Applications to Interlacing Families Anari, N., Gharan, S., Saberi, A., Srivastava, N., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1015–28
  • Diffusion, Seeding, and the Value of Network Information Akbarpour, M., Malladi, S., Saberi, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 641
  • Creating Crowdsourced Research Talks at Scale Vaish, R., Goyal, S., Saberi, A., Goel, S., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1–11
  • Approximation Algorithms for Computing Maximin Share Allocations ACM TRANSACTIONS ON ALGORITHMS Amanatidis, G., Markakis, E., Nikzad, A., Saberi, A. 2017; 13 (4)

    View details for DOI 10.1145/3147173

    View details for Web of Science ID 000419242000009

  • An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem OPERATIONS RESEARCH Asadpour, A., Goemans, M. X., Madry, A., Gharan, S., Saberi, A. 2017; 65 (4): 1043-1061
  • How Gamification Affects Physical Activity: Large-scale Analysis of Walking Challenges in a Mobile Application. Proceedings of the ... International World-Wide Web Conference. International WWW Conference Shameli, A., Althoff, T., Saberi, A., Leskovec, J. 2017; 2017: 455–63

    Abstract

    Gamification represents an effective way to incentivize user behavior across a number of computing applications. However, despite the fact that physical activity is essential for a healthy lifestyle, surprisingly little is known about how gamification and in particular competitions shape human physical activity. Here we study how competitions affect physical activity. We focus on walking challenges in a mobile activity tracking application where multiple users compete over who takes the most steps over a predefined number of days. We synthesize our findings in a series of game and app design implications. In particular, we analyze nearly 2,500 physical activity competitions over a period of one year capturing more than 800,000 person days of activity tracking. We observe that during walking competitions, the average user increases physical activity by 23%. Furthermore, there are large increases in activity for both men and women across all ages, and weight status, and even for users that were previously fairly inactive. We also find that the composition of participants greatly affects the dynamics of the game. In particular, if highly unequal participants get matched to each other, then competition suffers and the overall effect on the physical activity drops significantly. Furthermore, competitions with an equal mix of both men and women are more effective in increasing the level of activities. We leverage these insights to develop a statistical model to predict whether or not a competition will be particularly engaging with significant accuracy. Our models can serve as a guideline to help design more engaging competitions that lead to most beneficial behavioral changes.

    View details for PubMedID 28990011

  • Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices Anari, N., Gurvits, L., Gharan, S., Saberi, A., IEEE IEEE. 2017: 914–25
  • Mobilizing the Crowd to Create an Open Repository of Research Talks Vaish, R., Goel, S., Saberi, A., ACM ASSOC COMPUTING MACHINERY. 2017: 311-314
  • A Simple and Efficient Algorithm for Computing Market Equilibria ACM TRANSACTIONS ON ALGORITHMS Fleischer, L., Garg, R., Kapoor, S., Khandekar, R., Saberi, A. 2016; 12 (3)

    View details for DOI 10.1145/2905372

    View details for Web of Science ID 000379424200008

  • Approximation Algorithms for Computing Maximin Share Allocations Amanatidis, G., Markakis, E., Nikzad, A., Saberi, A., Halldorsson, M. M., Iwama, K., Kobayashi, N., Speckmann, B. SPRINGER-VERLAG BERLIN. 2015: 39-51
  • ASYMPTOTIC BEHAVIOR AND DISTRIBUTIONAL LIMITS OF PREFERENTIAL ATTACHMENT GRAPHS ANNALS OF PROBABILITY Berger, N., Borgs, C., Chayes, J. T., Saberi, A. 2014; 42 (1): 1-40

    View details for DOI 10.1214/12-AOP755

    View details for Web of Science ID 000330253800001

  • Message-Passing Algorithms for Sparse Network Alignment ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA Bayati, M., Gleich, D. F., Saberi, A., Wang, Y. 2013; 7 (1)
  • Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising OPERATIONS RESEARCH Nazerzadeh, H., Saberi, A., Vohra, R. 2013; 61 (1): 98-111
  • Algorithmic Solutions for Envy-Free Cake Cutting OPERATIONS RESEARCH Deng, X., Qi, Q., Saberi, A. 2012; 60 (6): 1461-1476
  • Online Stochastic Matching: Online Actions Based on Offline Statistics MATHEMATICS OF OPERATIONS RESEARCH Manshadi, V. H., Gharan, S. O., Saberi, A. 2012; 37 (4): 559-573
  • Santa Claus Meets Hypergraph Matchings ACM TRANSACTIONS ON ALGORITHMS Asadpour, A., Feige, U., Saberi, A. 2012; 8 (3)
  • Online Optimization with Uncertain Information ACM TRANSACTIONS ON ALGORITHMS Mahdian, M., Nazerzadeh, H., Saberi, A. 2012; 8 (1)
  • Distributed Node Placement Algorithms for Constructing Well-Connected Sensor Networks IEEE INFOCOM Conference Friend, A. J., Manshadi, V. H., Saberi, A. IEEE. 2012: 810–818
  • Price of Correlations in Stochastic Optimization OPERATIONS RESEARCH Agrawal, S., Ding, Y., Saberi, A., Ye, Y. 2012; 60 (1): 150-162
  • Discrete Fixed Points: Models, Complexities, and Applications MATHEMATICS OF OPERATIONS RESEARCH Deng, X., Qi, Q., Saberi, A., Zhang, J. 2011; 36 (4): 636-652
  • Some computational tools for digital archive and metadata maintenance BIT NUMERICAL MATHEMATICS Gleich, D. F., Wang, Y., Meng, X., Ronaghi, F., Gerritsen, M., Saberi, A. 2011; 51 (1): 127-154
  • Social Influence and Evolution of Market Share INTERNET MATHEMATICS Ceyhan, S., Mousavi, M., Saberi, A. 2011; 7 (2): 107-134
  • Online Stochastic Matching: Online Actions Based on Offline Statistics 22nd Annual ACM/SIAM Symposium on Discrete Algorithms Manshadi, V. H., Gharan, S. O., Saberi, A. SIAM. 2011: 1285–1294
  • A Randomized Rounding Approach to the Traveling Salesman Problem 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) Gharan, S. O., Saberi, A., Singh, M. IEEE COMPUTER SOC. 2011: 550–559
  • The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus 22nd Annual ACM/SIAM Symposium on Discrete Algorithms Gharan, S. O., Saberi, A. SIAM. 2011: 967–975
  • A Sequential Algorithm for Generating Random Graphs ALGORITHMICA Bayati, M., Kim, J. H., Saberi, A. 2010; 58 (4): 860-910
  • The spread of innovations in social networks PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA Montanari, A., Saberi, A. 2010; 107 (47): 20196-20201

    Abstract

    Which network structures favor the rapid spread of new ideas, behaviors, or technologies? This question has been studied extensively using epidemic models. Here we consider a complementary point of view and consider scenarios where the individuals' behavior is the result of a strategic choice among competing alternatives. In particular, we study models that are based on the dynamics of coordination games. Classical results in game theory studying this model provide a simple condition for a new action or innovation to become widespread in the network. The present paper characterizes the rate of convergence as a function of the structure of the interaction network. The resulting predictions differ strongly from the ones provided by epidemic models. In particular, it appears that innovation spreads much more slowly on well-connected network structures dominated by long-range links than in low-dimensional ones dominated, for example, by geographic proximity.

    View details for DOI 10.1073/pnas.1004098107

    View details for Web of Science ID 000284529000013

    View details for PubMedID 21076030

    View details for PubMedCentralID PMC2996710

  • Advertisement allocation for generalized second-pricing schemes OPERATIONS RESEARCH LETTERS Goel, A., Mahdian, M., Nazerzadeh, H., Saberi, A. 2010; 38 (6): 571-576
  • How to Distribute Antidote to Control Epidemics RANDOM STRUCTURES & ALGORITHMS Borgs, C., Chayes, J., Ganesh, A., Saberi, A. 2010; 37 (2): 204-222

    View details for DOI 10.1002/rsa.20315

    View details for Web of Science ID 000281045300003

  • On the Dynamic Response of a Saturating Static Feedback-Controlled Single Integrator Driven by White Noise IEEE TRANSACTIONS ON AUTOMATIC CONTROL Wen, Z., Roy, S., Saberi, A. 2010; 55 (4): 959-965
  • Approximating power indices: theoretical and empirical analysis AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS Bachrach, Y., Markakis, E., Resnick, E., Procaccia, A. D., Rosenschein, J. S., Saberi, A. 2010; 20 (2): 105-122
  • An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem 21st Annual ACM/SIAM Symposium on Discrete Algorithms Asadpour, A., Goemans, M. X., Madry, A., Gharan, S. O., Saberi, A. SIAM. 2010: 379–389
  • Correlation Robust Stochastic Optimization 21st Annual ACM/SIAM Symposium on Discrete Algorithms Agrawal, S., Ding, Y., Saberi, A., Ye, Y. SIAM. 2010: 1087–1096
  • Subgraph Sparsification and Nearly Optimal Ultrasparsifiers 42nd ACM Symposium on Theory of Computing Kolla, A., Makarychev, Y., Saberi, A., Teng, S. ASSOC COMPUTING MACHINERY. 2010: 57–65
  • AN APPROXIMATION ALGORITHM FOR MAX-MIN FAIR ALLOCATION OF INDIVISIBLE GOODS SIAM JOURNAL ON COMPUTING Asadpour, A., Saberi, A. 2010; 39 (7): 2970-2989

    View details for DOI 10.1137/080723491

    View details for Web of Science ID 000280847900010

  • Convergence to Equilibrium in Local Interaction Games SI GECOM EXCHANGES Montanari, A., Saberi, A. 2009; 8 (1)
  • Cutting a Cake for Five People 5th International Conference on Algorithmic Aspects in Information and Management Saberi, A., Wang, Y. SPRINGER-VERLAG BERLIN. 2009: 292–300
  • Convergence to Equilibrium in Local Interaction Games 50th Annual IEEE Symposium on Foundations of Computer Science Montanari, A., Saberi, A. IEEE COMPUTER SOC. 2009: 303–312
  • Generating random Tanner-graphs with large girth IEEE Information Theory Workshop (ITW) Bayati, M., Keshavan, R., Montanari, A., Oh, S., Saberi, A. IEEE. 2009: 154–157
  • Generating Random Graphs with Large Girth 20th Annual ACM-SIAM Symposium on Discrete Algorithms Bayati, M., Montanari, A., Saberi, A. SIAM. 2009: 566–575
  • On the Inefficiency Ratio of Stable Equilibria in Congestion Games 5th International Workshop on Internet and Network Economics Asadpour, A., Saberi, A. SPRINGER-VERLAG BERLIN. 2009: 545–552
  • Algorithms for Large, Sparse Network Alignment Problems 9th IEEE International Conference on Data Mining Bayati, M., Gerritsen, M., Gleich, D. F., Saberi, A., Wang, Y. IEEE. 2009: 705–710
  • The complexity of equilibria: Hardness results for economies via a correspondence with games Workshop on Excursions in Algoritmics Codenotti, B., Saberi, A., Varadarajan, K., Ye, Y. ELSEVIER SCIENCE BV. 2008: 188–98
  • Market Equilibrium via a Primal-Dual Algorithm for a Convex Program JOURNAL OF THE ACM Devanur, N. R., Papadimitriou, C. H., Saberi, A., Vazirani, V. V. 2008; 55 (5)
  • On the disturbance response and external stability of a saturating static-feedback-controlled double integrator AUTOMATICA Wen, Z., Roy, S., Saberi, A. 2008; 44 (8): 2191-2196
  • A Monte Carlo method for solving unsteady adjoint equations JOURNAL OF COMPUTATIONAL PHYSICS Wang, Q., Gleich, D., Saberi, A., Etemadi, N., Moin, P. 2008; 227 (12): 6184-6205
  • Minimizing effective resistance of a graph SIAM REVIEW Ghosh, A., Boyd, S., Saberi, A. 2008; 50 (1): 37-66

    View details for DOI 10.1137/050645452

    View details for Web of Science ID 000253646600004

  • Stochastic Submodular Maximization 4th International Workshop on Internet and Network Economics Asadpour, A., Nazerzadeh, H., Saberi, A. SPRINGER-VERLAG BERLIN. 2008: 477–489
  • A Fast and Simple Algorithm for Computing Market Equilibria 4th International Workshop on Internet and Network Economics Fleischer, L., Garg, R., Kapoor, S., Khandekar, R., Saberi, A. SPRINGER-VERLAG BERLIN. 2008: 19–30
  • Santa Claus Meets Hypergraph Matchings 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/12th International Workshop on Randomization and Computation Asadpour, A., Feige, U., Saberi, A. SPRINGER-VERLAG BERLIN. 2008: 10–20
  • Cell breathing in wireless LANs: Algorithms and evaluation IEEE TRANSACTIONS ON MOBILE COMPUTING Bahl, P. (., Hajiaghayi, M. T., Jain, K., Mirrokni, S. V., Qiu, L., Saberi, A. 2007; 6 (2): 164-178
  • AdWords and generalized Online matching JOURNAL OF THE ACM Mehta, A., Saberi, A., Vazirani, U., Vazirani, V. 2007; 54 (5)
  • Sponsored Search Auctions ALGORITHMIC GAME THEORY Lahaie, S., Pennock, D. M., Saberi, A., Vohra, R. V., Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. V. 2007: 699-716
  • An Approximation Alaorithm for Max-Min Fair Allocation of Indivisible Goods 39th Annual ACM Symposium on Theory of Computing Asadpour, A., Saberi, A. ASSOC COMPUTING MACHINERY. 2007: 114–121
  • Allocating Online Advertisement Space with Unreliable Estimates 8th Annual Conference on Electronic Commerce (EC 2007) Mahdian, M., Nazerzadeh, H., Saberi, A. ASSOC COMPUTING MACHINERY. 2007: 288–294
  • Towards topology aware networks 26th IEEE Conference on Computer Communications (INFOCOM 2007) Gkantsidis, C., Goel, G., Mihail, M., Saberi, A. IEEE. 2007: 2591–2595
  • Approximating Nash Equilibria using Small-Support Strategies 8th Annual Conference on Electronic Commerce (EC 2007) Feder, T., Nazerzadeh, H., Saberi, A. ASSOC COMPUTING MACHINERY. 2007: 352–354
  • A sequential algorithm for generating random graphs 10th Int Workshop on Approximation Algorithms for Combinatorial Optimization Problems/11th Int Workshop on Randomization and Computation Bayati, M., Kim, J. H., Saberi, A. SPRINGER-VERLAG BERLIN. 2007: 326–340
  • On certain connectivity properties of the Internet topology 44th Annual IEEE Symposium on Foundations of Computer Science Mihail, M., Papadimitriou, C., Saberi, A. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2006: 239–51
  • Random walks in peer-to-peer networks: Algorithms and evaluation PERFORMANCE EVALUATION Gkantsidis, C., Mihail, M., Saberi, A. 2006; 63 (3): 241-263
  • Random Walks with Lookahead on Power Law Random Graphs INTERNET MATHEMATICS Mihail, M., Saberi, A., Tetali, P. 2006; 3 (2): 147-152
  • Leontief Economies Encode Nonzero Sum Two-Player Games 17th ACM-SIAM Symposium on Discrete Algorithms Codenotti, B., Saberi, A., Varadarajan, K., Ye, Y. SIAM. 2006: 659–667
  • A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks 47th Annual IEEE Symposium on Foundations of Computer Science Feder, T., Guetz, A., Mihail, M., Saberi, A. IEEE COMPUTER SOC. 2006: 69–76
  • On the core of the multicommodity flow game 4th ACM Conference on Electronics Commerce (EC'03) Markakis, E., Saberi, A. ELSEVIER SCIENCE BV. 2005: 3–10
  • Hybrid search schemes for unstructured peer-to-peer networks 24th Annual Joint Conference of the IEEE Computer and Communications Societies Gkantsidis, C., Mihail, N., Saberi, A. IEEE COMPUTER SOC. 2005: 1526–1537
  • On the Spread of Viruses on the Internet 16th Annual ACM-SIAM Symposium on Discrete Algorithms Berger, N., Borgs, C., Chayes, J. T., Saberi, A. SIAM. 2005: 301–310
  • Price of anarchy, locality gap, and a network service provider game 1st International Workshop on Internet and Network Economics Devanur, N., Garg, N., Khandekar, R., Pandit, V., Saberi, A., Vazirani, V. SPRINGER-VERLAG BERLIN. 2005: 1046–1055
  • Random walks in peer-to-peer networks 23rd Annual Joint Conference of the IEEE Computer and Communications Societies Gkantsidis, C., Mihail, M., Saberi, A. IEEE. 2004: 120–130
  • Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP JOURNAL OF THE ACM Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V. V. 2003; 50 (6): 795-824
  • Approximating market equilibria 6th Int Workshop on Approximation Algorithms for Combinatorial Optimization Problems/7th Int Workshop on Randomization and Approximation Techniques in Computer Science Jain, K., Mahdian, M., Saberi, A. SPRINGER-VERLAG BERLIN. 2003: 98–108
  • On certain connectivity properties of the Internet topology 44th Annual IEEE Symposium on Foundations of Computer Science Mihail, M., Papadimitriou, C., Saberi, A. IEEE COMPUTER SOC. 2003: 28–35
  • On the hardness of optimal auctions 43rd Annual IEEE Symposium on Foundations of Computer Science Ronen, A., Saberi, A. IEEE COMPUTER SOC. 2002: 396–405
  • Market equilibrium via a primal-dual-type algorithm 43rd Annual IEEE Symposium on Foundations of Computer Science Devanur, N. R., Papadimitriou, C. H., Saberi, A., Vazirani, V. V. IEEE COMPUTER SOC. 2002: 389–395
  • A greedy facility location algorithm analyzed using dual fitting 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/5th Int Workshop on Randomization and Approximation Techniques in Comp Sci Mahdian, M., Markakis, E., Saberi, A., Vazirani, V. SPRINGER-VERLAG BERLIN. 2001: 127–137
  • On a conjecture of Keedwell and the cycle double cover conjecture DISCRETE MATHEMATICS Mahdian, M., Mahmoodian, E. S., Saberi, A., Salavatipour, M. R., Tusserkani, R. 2000; 216 (1-3): 287-292