Bio


Amin Saberi is an Associate Professor and 3COM faculty scholar in 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, approximation algorithms, and algorithmic aspects of games, markets, and networks. Amin Saberi's research is supported by National Science Foundation (under grants CCF 0546889, 0729586, and 0915145), Library of Congress, Stanford Clean Slate Design for the Internet, and Google. His most recent awards include an Alfred Sloan Fellowship and best paper awards in FOCS 2011 and SODA 2010.

Academic Appointments


Professional Education


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

2017-18 Courses


Stanford Advisees


All Publications


  • 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)
  • Price of Correlations in Stochastic Optimization OPERATIONS RESEARCH Agrawal, S., Ding, Y., Saberi, A., Ye, Y. 2012; 60 (1): 150-162
  • 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
  • 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
  • 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
  • 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
  • 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

  • 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
  • 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

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