Amin Saberi
Professor of Management Science and Engineering and, by courtesy, of Computer Science
Web page: http://web.stanford.edu/~saberi
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
-
Professor, Management Science and Engineering
-
Professor (By courtesy), Computer Science
-
Member, Bio-X
Professional Education
-
BS, Sharif Institute of Technology, Tehran, Iran, Computer Science (2000)
-
PhD, Georgia Institute of Technology, Computer Science (2004)
2024-25 Courses
- Introduction to Optimization: Data Science
MS&E 111DS, MS&E 211DS (Win) - Matching Theory
MS&E 319 (Spr) - Senior Project
MS&E 108 (Win) -
Independent Studies (7)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Directed Reading and Research
MS&E 408 (Aut, Win, Spr) - Independent Project
CS 399 (Aut) - Part-time Curricular Practical Training
CS 390D (Aut, Win, Spr) - Ph.D. Research
CME 400 (Aut, Win, Spr) - Writing Intensive Senior Research Project
CS 191W (Aut, Win, Spr)
- Advanced Reading and Research
-
Prior Year Courses
2023-24 Courses
- Graph and Combinatorial Optimization
MS&E 112, MS&E 212 (Win) - Introduction to Optimization: Data Science
MS&E 111DS, MS&E 211DS (Win) - Large Networks and Graph Limits
MS&E 337 (Aut)
2021-22 Courses
- Market Design in Action
MS&E 239 (Spr) - Matching Theory
MS&E 319 (Spr) - Mathematical Programming and Combinatorial Optimization
MS&E 112, MS&E 212 (Aut)
- Graph and Combinatorial Optimization
Stanford Advisees
-
Doctoral Dissertation Reader (AC)
Mohak Goyal -
Doctoral Dissertation Advisor (AC)
Tristan Pollner, Mohammad Roghani -
Master's Program Advisor
Shea Burcham, Aurnov Chattopadhyay, Feona Dong, Drew Gao, Elizabeth Griffin, Kent Hippler, Lucy Jiang, Soo Rim (Hannah) Lee, Manish Raj, Keshav Sivakumar -
Doctoral (Program)
Kiana Asgari, Elaine Liu, Shayan Talaei, Mingwei Yang
All Publications
-
Assignment Mechanisms Under Distributional Constraints
OPERATIONS RESEARCH
2020; 68 (2): 467–79
View details for DOI 10.1287/opre.2019.1887
View details for Web of Science ID 000521730200009
-
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection
ASSOC COMPUTING MACHINERY. 2019: 91–92
View details for DOI 10.1145/3328526.3329652
View details for Web of Science ID 000483848100012
-
Competition in Ride-Hailing Markets
SPRINGER INTERNATIONAL PUBLISHING AG. 2019: 333
View details for DOI 10.1007/978-3-030-35389-6
View details for Web of Science ID 000611509000024
-
Edge Weighted Online Windowed Matching
ASSOC COMPUTING MACHINERY. 2019: 729–42
View details for DOI 10.1145/3328526.3329573
View details for Web of Science ID 000483848100085
-
Generating Random Networks Without Short Cycles
OPERATIONS RESEARCH
2018; 66 (5): 1227–46
View details for DOI 10.1287/opre.2018.1730
View details for Web of Science ID 000446179500004
-
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018
View details for Web of Science ID 000461852005044
-
Approximating the Largest Root and Applications to Interlacing Families
ASSOC COMPUTING MACHINERY. 2018: 1015–28
View details for Web of Science ID 000483921200067
-
Diffusion, Seeding, and the Value of Network Information
ASSOC COMPUTING MACHINERY. 2018: 641
View details for Web of Science ID 000492755100068
-
Creating Crowdsourced Research Talks at Scale
ASSOC COMPUTING MACHINERY. 2018: 1–11
View details for DOI 10.1145/3178876.3186031
View details for Web of Science ID 000460379000001
-
Approximation Algorithms for Computing Maximin Share Allocations
ACM TRANSACTIONS ON ALGORITHMS
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
2017; 65 (4): 1043-1061
View details for DOI 10.1287/opre.2017.1603
View details for Web of Science ID 000406488600009
-
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
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
IEEE. 2017: 914–25
View details for DOI 10.1109/FOCS.2017.89
View details for Web of Science ID 000417425300080
-
Mobilizing the Crowd to Create an Open Repository of Research Talks
ASSOC COMPUTING MACHINERY. 2017: 311-314
View details for DOI 10.1145/3051457.3054012
View details for Web of Science ID 000630169200061
-
A Simple and Efficient Algorithm for Computing Market Equilibria
ACM TRANSACTIONS ON ALGORITHMS
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
SPRINGER-VERLAG BERLIN. 2015: 39-51
View details for DOI 10.1007/978-3-662-47672-7_4
View details for Web of Science ID 000364317700004
-
ASYMPTOTIC BEHAVIOR AND DISTRIBUTIONAL LIMITS OF PREFERENTIAL ATTACHMENT GRAPHS
ANNALS OF PROBABILITY
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
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
2013; 61 (1): 98-111
View details for DOI 10.1287/opre.1120.1124
View details for Web of Science ID 000316115000008
-
Online Stochastic Matching: Online Actions Based on Offline Statistics
MATHEMATICS OF OPERATIONS RESEARCH
2012; 37 (4): 559-573
View details for DOI 10.1287/moor.1120.0551
View details for Web of Science ID 000314284200001
-
Algorithmic Solutions for Envy-Free Cake Cutting
OPERATIONS RESEARCH
2012; 60 (6): 1461-1476
View details for DOI 10.1287/opre.1120.1116
View details for Web of Science ID 000312468800012
-
Santa Claus Meets Hypergraph Matchings
ACM TRANSACTIONS ON ALGORITHMS
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
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
IEEE. 2012: 810–818
View details for Web of Science ID 000309279500091
-
Price of Correlations in Stochastic Optimization
OPERATIONS RESEARCH
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
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
2011; 51 (1): 127-154
View details for DOI 10.1007/s10543-011-0324-6
View details for Web of Science ID 000288707100007
-
Online Stochastic Matching: Online Actions Based on Offline Statistics
22nd Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2011: 1285–1294
View details for Web of Science ID 000296182400098
-
A Randomized Rounding Approach to the Traveling Salesman Problem
52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)
IEEE COMPUTER SOC. 2011: 550–559
View details for DOI 10.1109/FOCS.2011.80
View details for Web of Science ID 000298962700059
-
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
22nd Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2011: 967–975
View details for Web of Science ID 000296182400075
-
Social Influence and Evolution of Market Share
INTERNET MATHEMATICS
2011; 7 (2): 107-134
View details for DOI 10.1080/15427951.2011.579849
View details for Web of Science ID 000217667500002
-
A Sequential Algorithm for Generating Random Graphs
ALGORITHMICA
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
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
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
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
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
2010; 20 (2): 105-122
View details for DOI 10.1007/s10458-009-9078-9
View details for Web of Science ID 000273978500001
-
Correlation Robust Stochastic Optimization
21st Annual ACM/SIAM Symposium on Discrete Algorithms
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
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
2010; 39 (7): 2970-2989
View details for DOI 10.1137/080723491
View details for Web of Science ID 000280847900010
-
An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem
21st Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2010: 379–389
View details for Web of Science ID 000280699900032
-
Convergence to Equilibrium in Local Interaction Games
SI GECOM EXCHANGES
2009; 8 (1)
View details for Web of Science ID 000218490200010
-
Algorithms for Large, Sparse Network Alignment Problems
9th IEEE International Conference on Data Mining
IEEE. 2009: 705–710
View details for Web of Science ID 000287216600074
-
On the Inefficiency Ratio of Stable Equilibria in Congestion Games
5th International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2009: 545–552
View details for Web of Science ID 000278097500054
-
Cutting a Cake for Five People
5th International Conference on Algorithmic Aspects in Information and Management
SPRINGER-VERLAG BERLIN. 2009: 292–300
View details for Web of Science ID 000268031100023
-
Convergence to Equilibrium in Local Interaction Games
50th Annual IEEE Symposium on Foundations of Computer Science
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)
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
SIAM. 2009: 566–575
View details for Web of Science ID 000281447000063
-
The complexity of equilibria: Hardness results for economies via a correspondence with games
Workshop on Excursions in Algoritmics
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
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
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
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
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
SPRINGER-VERLAG BERLIN. 2008: 477–489
View details for Web of Science ID 000262046200044
-
Santa Claus Meets Hypergraph Matchings
11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/12th International Workshop on Randomization and Computation
SPRINGER-VERLAG BERLIN. 2008: 10–20
View details for Web of Science ID 000260573700002
-
A Fast and Simple Algorithm for Computing Market Equilibria
4th International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2008: 19–30
View details for Web of Science ID 000262046200002
-
Cell breathing in wireless LANs: Algorithms and evaluation
IEEE TRANSACTIONS ON MOBILE COMPUTING
2007; 6 (2): 164-178
View details for Web of Science ID 000242856000003
-
AdWords and generalized Online matching
JOURNAL OF THE ACM
2007; 54 (5)
View details for DOI 10.1145/1284320.1284321
View details for Web of Science ID 000250557900001
-
Sponsored Search Auctions
ALGORITHMIC GAME THEORY
2007: 699-716
View details for Web of Science ID 000296374200030
-
Towards topology aware networks
26th IEEE Conference on Computer Communications (INFOCOM 2007)
IEEE. 2007: 2591–2595
View details for Web of Science ID 000249117704087
-
An Approximation Alaorithm for Max-Min Fair Allocation of Indivisible Goods
39th Annual ACM Symposium on Theory of Computing
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
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)
ASSOC COMPUTING MACHINERY. 2007: 288–294
View details for Web of Science ID 000268330200034
-
Approximating Nash Equilibria using Small-Support Strategies
8th Annual Conference on Electronic Commerce (EC 2007)
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
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
-
Random walks in peer-to-peer networks: Algorithms and evaluation
PERFORMANCE EVALUATION
2006; 63 (3): 241-263
View details for DOI 10.1016/j.peva.2005.01.002
View details for Web of Science ID 000235488900006
-
Leontief Economies Encode Nonzero Sum Two-Player Games
17th ACM-SIAM Symposium on Discrete Algorithms
SIAM. 2006: 659–667
View details for Web of Science ID 000281596300072
-
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
IEEE COMPUTER SOC. 2006: 69–76
View details for Web of Science ID 000242526200007
-
Random Walks with Lookahead on Power Law Random Graphs
INTERNET MATHEMATICS
2006; 3 (2): 147-152
View details for DOI 10.1080/15427951.2006.10129122
View details for Web of Science ID 000217623700002
-
On the core of the multicommodity flow game
4th ACM Conference on Electronics Commerce (EC'03)
ELSEVIER SCIENCE BV. 2005: 3–10
View details for DOI 10.1016/j.dss.2004.08.003
View details for Web of Science ID 000226229500002
-
Hybrid search schemes for unstructured peer-to-peer networks
24th Annual Joint Conference of the IEEE Computer and Communications Societies
IEEE COMPUTER SOC. 2005: 1526–1537
View details for Web of Science ID 000231441002003
-
On the Spread of Viruses on the Internet
16th Annual ACM-SIAM Symposium on Discrete Algorithms
SIAM. 2005: 301–310
View details for Web of Science ID 000281595800035
-
Price of anarchy, locality gap, and a network service provider game
1st International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2005: 1046–1055
View details for Web of Science ID 000234851600105
-
Random walks in peer-to-peer networks
23rd Annual Joint Conference of the IEEE Computer and Communications Societies
IEEE. 2004: 120–130
View details for Web of Science ID 000223848100012
-
Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP
JOURNAL OF THE ACM
2003; 50 (6): 795-824
View details for Web of Science ID 000186728500001
-
On certain connectivity properties of the Internet topology
44th Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2003: 28–35
View details for Web of Science ID 000186758200005
-
Approximating market equilibria
6th Int Workshop on Approximation Algorithms for Combinatorial Optimization Problems/7th Int Workshop on Randomization and Approximation Techniques in Computer Science
SPRINGER-VERLAG BERLIN. 2003: 98–108
View details for Web of Science ID 000185994700009
-
On the hardness of optimal auctions
43rd Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2002: 396–405
View details for Web of Science ID 000179945300040
-
Market equilibrium via a primal-dual-type algorithm
43rd Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2002: 389–395
View details for Web of Science ID 000179945300039
-
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
SPRINGER-VERLAG BERLIN. 2001: 127–137
View details for Web of Science ID 000180456300016
-
On a conjecture of Keedwell and the cycle double cover conjecture
DISCRETE MATHEMATICS
2000; 216 (1-3): 287-292
View details for Web of Science ID 000086350600021