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)

2013-14 Courses


Journal Articles


  • 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 2012 PROCEEDINGS IEEE INFOCOM Friend, A. J., Manshadi, V. H., Saberi, A. 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 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011) Gharan, S. O., Saberi, A., Singh, M. 2011: 550-559
  • Online Stochastic Matching: Online Actions Based on Offline Statistics PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Manshadi, V. H., Gharan, S. O., Saberi, A. 2011: 1285-1294
  • The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Gharan, S. O., Saberi, A. 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 PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Asadpour, A., Goemans, M. X., Madry, A., Gharan, S. O., Saberi, A. 2010; 135: 379-389
  • Correlation Robust Stochastic Optimization PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Agrawal, S., Ding, Y., Saberi, A., Ye, Y. 2010; 135: 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 STOC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON THEORY OF COMPUTING Kolla, A., Makarychev, Y., Saberi, A., Teng, S. 2010: 57-65
  • Cutting a Cake for Five People ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS Saberi, A., Wang, Y. 2009; 5564: 292-300
  • Convergence to Equilibrium in Local Interaction Games 2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS Montanari, A., Saberi, A. 2009: 303-312
  • Generating random Tanner-graphs with large girth 2009 IEEE INFORMATION THEORY WORKSHOP (ITW 2009) Bayati, M., Keshavan, R., Montanari, A., Oh, S., Saberi, A. 2009: 154-157
  • Generating Random Graphs with Large Girth PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Bayati, M., Montanari, A., Saberi, A. 2009: 566-575
  • On the Inefficiency Ratio of Stable Equilibria in Congestion Games INTERNET AND NETWORK ECONOMICS, PROCEEDINGS Asadpour, A., Saberi, A. 2009; 5929: 545-552
  • Algorithms for Large, Sparse Network Alignment Problems 2009 9TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING Bayati, M., Gerritsen, M., Gleich, D. F., Saberi, A., Wang, Y. 2009: 705-710
  • 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 INTERNET AND NETWORK ECONOMICS, PROCEEDINGS Asadpour, A., Nazerzadeh, H., Saberi, A. 2008; 5385: 477-489
  • A Fast and Simple Algorithm for Computing Market Equilibria INTERNET AND NETWORK ECONOMICS, PROCEEDINGS Fleischer, L., Garg, R., Kapoor, S., Khandekar, R., Saberi, A. 2008; 5385: 19-30
  • Santa Claus Meets Hypergraph Matchings APPROXIMATION RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS Asadpour, A., Feige, U., Saberi, A. 2008; 5171: 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 STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING Asadpour, A., Saberi, A. 2007: 114-121
  • A sequential algorithm for generating random graphs APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES Bayati, M., Kim, J. H., Saberi, A. 2007; 4627: 326-340
  • Allocating Online Advertisement Space with Unreliable Estimates EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE Mahdian, M., Nazerzadeh, H., Saberi, A. 2007: 288-294
  • Towards topology aware networks INFOCOM 2007, VOLS 1-5 Gkantsidis, C., Goel, G., Mihail, M., Saberi, A. 2007: 2591-2595
  • Approximating Nash Equilibria using Small-Support Strategies EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE Feder, T., Nazerzadeh, H., Saberi, A. 2007: 352-354
  • 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, PROCEEDINGS Feder, T., Guetz, A., Mihail, M., Saberi, A. 2006: 69-76
  • Leontief Economies Encode Nonzero Sum Two-Player Games PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS Codenotti, B., Saberi, A., Varadarajan, K., Ye, Y. 2006: 659-667
  • Hybrid search schemes for unstructured peer-to-peer networks IEEE INFOCOM 2005: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-4, PROCEEDINGS Gkantsidis, C., Mihail, N., Saberi, A. 2005: 1526-1537
  • Price of anarchy, locality gap, and a network service provider game INTERNET AND NETWORK ECONOMICS, PROCEEDINGS Devanur, N., Garg, N., Khandekar, R., Pandit, V., Saberi, A., Vazirani, V. 2005; 3828: 1046-1055
  • On the hardness of optimal auctions FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS Ronen, A., Saberi, A. 2002: 396-405

Conference Proceedings