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)

Contact

  • Academic
    saberi@stanford.edu
    University - Faculty Department: Management Science and Engineering Position: Professor
    • 309, Huang Engineering Center
    • 475 Via Ortega Stanford
    • Stanford,  California  94305 

Additional Info

  • Mail Code: 4026

2020-21 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)

    View details for DOI 10.1145/2435209.2435212

    View details for Web of Science ID 000316415700003

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

    View details for DOI 10.1287/opre.1120.1124

    View details for Web of Science ID 000316115000008

  • Algorithmic Solutions for Envy-Free Cake Cutting OPERATIONS RESEARCH Deng, X., Qi, Q., Saberi, A. 2012; 60 (6): 1461-1476

    View details for DOI 10.1287/opre.1120.1116

    View details for Web of Science ID 000312468800012

  • 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

    View details for DOI 10.1287/moor.1120.0551

    View details for Web of Science ID 000314284200001

  • Santa Claus Meets Hypergraph Matchings ACM TRANSACTIONS ON ALGORITHMS Asadpour, A., Feige, U., Saberi, A. 2012; 8 (3)

    View details for DOI 10.1145/2229163.2229168

    View details for Web of Science ID 000307170500005

  • Online Optimization with Uncertain Information ACM TRANSACTIONS ON ALGORITHMS Mahdian, M., Nazerzadeh, H., Saberi, A. 2012; 8 (1)

    View details for DOI 10.1145/2071379.2071381

    View details for Web of Science ID 000301391300002

  • 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

    View details for Web of Science ID 000309279500091

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

    View details for DOI 10.1287/opre.1110.1011

    View details for Web of Science ID 000302113900013

  • Discrete Fixed Points: Models, Complexities, and Applications MATHEMATICS OF OPERATIONS RESEARCH Deng, X., Qi, Q., Saberi, A., Zhang, J. 2011; 36 (4): 636-652

    View details for DOI 10.1287/moor.1110.0511

    View details for Web of Science ID 000296977700004

  • 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

    View details for DOI 10.1007/s10543-011-0324-6

    View details for Web of Science ID 000288707100007

  • 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

    View details for DOI 10.1109/FOCS.2011.80

    View details for Web of Science ID 000298962700059

  • 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

    View details for Web of Science ID 000296182400098

  • 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

    View details for Web of Science ID 000296182400075

  • A Sequential Algorithm for Generating Random Graphs ALGORITHMICA Bayati, M., Kim, J. H., Saberi, A. 2010; 58 (4): 860-910

    View details for DOI 10.1007/s00453-009-9340-1

    View details for Web of Science ID 000282089900003

  • 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

    View details for DOI 10.1016/j.orl.2010.09.002

    View details for Web of Science ID 000284496700018

  • 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

    View details for DOI 10.1109/TAC.2010.2041608

    View details for Web of Science ID 000276251300014

  • 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

    View details for DOI 10.1007/s10458-009-9078-9

    View details for Web of Science ID 000273978500001

  • 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

    View details for Web of Science ID 000280699900032

  • Correlation Robust Stochastic Optimization 21st Annual ACM/SIAM Symposium on Discrete Algorithms Agrawal, S., Ding, Y., Saberi, A., Ye, Y. SIAM. 2010: 1087–1096

    View details for Web of Science ID 000280699900088

  • 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

    View details for Web of Science ID 000286949900006

  • 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

  • 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

    View details for Web of Science ID 000268031100023

  • 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

    View details for Web of Science ID 000287216600074

  • 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

    View details for DOI 10.1109/FOCS.2009.64

    View details for Web of Science ID 000278330300030

  • 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

    View details for Web of Science ID 000305809200032

  • Generating Random Graphs with Large Girth 20th Annual ACM-SIAM Symposium on Discrete Algorithms Bayati, M., Montanari, A., Saberi, A. SIAM. 2009: 566–575

    View details for Web of Science ID 000281447000063

  • 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

    View details for Web of Science ID 000278097500054

  • 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

    View details for DOI 10.1016/j.tcs.2008.08.007

    View details for Web of Science ID 000261416700010

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

    View details for DOI 10.1145/1411509.1411512

    View details for Web of Science ID 000260916000003

  • 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

    View details for DOI 10.1016/j.automatica.2007.11.005

    View details for Web of Science ID 000258963700031

  • 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

    View details for DOI 10.1016/j.jcp.2008.03.006

    View details for Web of Science ID 000256502100012

  • 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

    View details for Web of Science ID 000262046200044

  • 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

    View details for Web of Science ID 000262046200002

  • 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

    View details for Web of Science ID 000260573700002

  • 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

    View details for Web of Science ID 000242856000003

  • AdWords and generalized Online matching JOURNAL OF THE ACM Mehta, A., Saberi, A., Vazirani, U., Vazirani, V. 2007; 54 (5)

    View details for DOI 10.1145/1284320.1284321

    View details for Web of Science ID 000250557900001

  • 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

    View details for Web of Science ID 000267050000013

  • 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

    View details for Web of Science ID 000250357100024

  • 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

    View details for Web of Science ID 000268330200034

  • Towards topology aware networks 26th IEEE Conference on Computer Communications (INFOCOM 2007) Gkantsidis, C., Goel, G., Mihail, M., Saberi, A. IEEE. 2007: 2591–2595

    View details for Web of Science ID 000249117704087

  • 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

    View details for Web of Science ID 000268330200041

  • 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

    View details for DOI 10.1016/j.jcss.2005.06.009

    View details for Web of Science ID 000236042100004

  • 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

    View details for Web of Science ID 000242526200007

  • 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

    View details for Web of Science ID 000281596300072

  • 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

    View details for Web of Science ID 000231441002003

  • 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

    View details for Web of Science ID 000234851600105

  • 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

    View details for Web of Science ID 000179945300040