Tim Roughgarden

Q: What Schools Are Affiliated With Tim Roughgarden

Tim Roughgarden is affiliated with the following schools: Stanford University, Cornell University, Columbia University

Tim Roughgarden's AcademicInfluence.com Rankings

Tim Roughgarden

Computer Science

#1064

World Rank

#1102

Historical Rank

#561

USA Rank

Database

#1207

World Rank

#1271

Historical Rank

#334

USA Rank

computer-science Degrees

Download Badge

Computer Science

Tim Roughgarden's Degrees

PhD Computer Science Cornell University
Bachelors Computer Science Stanford University

Similar Degrees You Can Earn

Why Is Tim Roughgarden Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.

(See a Problem?)

Tim Roughgarden's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Algorithmic game theory (2010) (2923)
How bad is selfish routing? (2000) (1909)
Selfish routing and the price of anarchy (2005) (928)
The price of stability for network design with fair cost allocation (2004) (920)
The price of anarchy is independent of the network topology (2002) (569)
Universally utility-maximizing privacy mechanisms (2008) (437)
Intrinsic robustness of the price of anarchy (2012) (386)
Bounding the inefficiency of equilibria in nonatomic congestion games (2004) (333)
Stackelberg scheduling strategies (2001) (327)
Simple versus optimal mechanisms (2009) (283)
Revenue maximization with a single sample (2010) (275)
Interactive privacy via the median mechanism (2009) (271)
Pricing network edges for heterogeneous selfish users (2003) (241)
The sample complexity of revenue maximization (2014) (236)
Climate change policy: quantifying uncertainties for damages and optimal carbon taxes (1999) (228)
Simpler and better approximation algorithms for network design (2003) (200)
How much can taxes help selfish routing? (2003) (199)
Optimal mechanism design and money burning (2008) (199)
Routers with Very Small Buffers (2006) (195)
Part III: routers with very small buffers (2005) (179)
On the severity of Braess's Paradox: Designing networks for selfish users is hard (2006) (166)
Almost Envy-Freeness with General Valuations (2017) (161)
Welfare guarantees for combinatorial auctions with item bidding (2011) (158)
Incentive Compatibility of Bitcoin Mining Pool Reward Functions (2016) (154)
Twenty Lectures on Algorithmic Game Theory (2016) (147)
On the Pseudo-Dimension of Nearly Optimal Auctions (2015) (136)
Network Design with Weighted Players (2006) (134)
Intrinsic Robustness of the Price of Anarchy (2015) (130)
Designing networks for selfish users is hard (2001) (123)
Making the Most of Your Samples (2014) (120)
Computing correlated equilibria in multi-player games (2008) (114)
Selfish Routing (2002) (112)
Computing equilibria in multi-player games (2005) (112)
Learning Simple Auctions (2016) (104)
Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation (2001) (102)
Preventing Unraveling in Social Networks: The Anchored k-Core Problem (2012) (94)
Planning Tours of Robotic Arms among Partitioned Goals (2006) (90)
Selfish routing with atomic players (2005) (89)
The price of anarchy in games of incomplete information (2012) (88)
Designing Network Protocols for Good Equilibria (2010) (86)
A PAC Approach to Application-Specific Algorithm Selection (2015) (86)
The Price of Anarchy in Auctions (2016) (82)
Beyond moulin mechanisms (2007) (81)
Algorithmic Game Theory: Introduction to the Inefficiency of Equilibria (2007) (78)
Private matchings and allocations (2013) (77)
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions (2011) (77)
The price of anarchy in an exponential multi-server (2007) (74)
How unfair is optimal routing? (2002) (73)
Weighted Congestion Games: The Price of Anarchy, Universal Worst-Case Examples, and Tightness (2014) (73)
Sketching valuation functions (2012) (72)
Truthful Approximation Schemes for Single-Parameter Agents (2008) (72)
Generalized Efficiency Bounds in Distributed Resource Allocation (2010) (71)
Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem (2003) (70)
Beyond worst-case analysis (2018) (68)
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002) (67)
Black-Box Randomized Reductions in Algorithmic Mechanism Design (2010) (66)
Local smoothness and the price of anarchy in splittable congestion games (2015) (65)
Designing networks with good equilibria (2008) (63)
Intrinsic robustness of the price of anarchy (2009) (63)
The maximum latency of selfish routing (2004) (62)
Braess's Paradox in large random graphs (2006) (61)
Fully Distributed Algorithms for Convex Optimization Problems (2007) (61)
Revenue submodularity (2009) (61)
Local smoothness and the price of anarchy in atomic splittable congestion games (2011) (60)
Ironing in the Dark (2015) (60)
The price of anarchy in large games (2015) (59)
New trade-offs in cost-sharing mechanisms (2006) (58)
Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation) (2016) (58)
Minimizing Regret with Multiple Reserves (2016) (56)
The price of anarchy in games of incomplete information (2012) (56)
Bertrand competition in networks (2008) (56)
Simple versus optimal mechanisms (2009) (53)
Proceedings of the 12th ACM conference on Electronic commerce (2011) (53)
Combinatorial auctions with restricted complements (2012) (52)
Privately Solving Linear Programs (2014) (52)
Modularity and greed in double auctions (2014) (52)
Restoring Pure Equilibria to Weighted Congestion Games (2011) (51)
Barriers to Near-Optimal Equilibria (2014) (50)
Is Shapley Cost Sharing Optimal? (2008) (48)
Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559 (2020) (48)
Computing equilibria: a computational complexity perspective (2015) (47)
Lightweight Coloring and Desynchronization for Networks (2009) (47)
Quantifying inefficiency in cost-sharing mechanisms (2009) (46)
The performance of deferred-acceptance auctions (2014) (46)
Approximation via cost sharing (2007) (46)
The Pseudo-Dimension of Near-Optimal Auctions (2015) (46)
An Axiomatic Approach to Block Rewards (2019) (44)
Simple versus Optimal Contracts (2018) (43)
Proceedings of the forty-fifth annual ACM symposium on Theory of computing (2013) (43)
Supply-limiting mechanisms (2012) (43)
Communication Complexity (for Algorithm Designers) (2015) (42)
Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing (2011) (41)
Bottleneck links, variable demand, and the tragedy of the commons (2006) (41)
Potential functions and the inefficiency of equilibria (2006) (40)
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization (2018) (40)
Algorithmic Game Theory: Routing Games (2007) (39)
Optimal and near-optimal mechanism design with interdependent values (2013) (38)
Optimal Cost-Sharing in General Resource Selection Games (2016) (38)
Finding Cliques in Social Networks: A New Distribution-Free Model (2018) (36)
Decompositions of triangle-dense graphs (2013) (35)
A stronger bound on Braess's Paradox (2004) (34)
The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds (2010) (33)
Approximately Efficient Two-Sided Combinatorial Auctions (2016) (33)
Transaction fee mechanism design (2021) (31)
Optimal Cost-Sharing Mechanisms for Steiner Forest Problems (2006) (31)
Data-driven algorithm design (2020) (30)
Network Cost-Sharing without Anonymity (2014) (29)
How Hard is Inference for Structured Prediction? (2015) (28)
How Bad is Selﬁsh Routing? ∗ (27)
Optimal Efficiency Guarantees for Network Design Mechanisms (2007) (26)
Public Projects, Boolean Functions, and the Borders of Border's Theorem (2015) (25)
Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness (2010) (24)
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability (2005) (24)
Is Efficiency Expensive (2007) (22)
Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation) (2018) (21)
Flexible Tree Matching (2011) (21)
Optimal and Robust Mechanism Design with Interdependent Values (2016) (21)
An Algorithmic Game Theory Primer (2008) (21)
Optimal Cost-Sharing in Weighted Congestion Games (2014) (21)
Why prices need algorithms (2015) (21)
Approximately Efficient Cost-Sharing Mechanisms (2006) (20)
The Complexity of Contracts (2020) (20)
Smoothed Analysis with Adaptive Adversaries (2021) (20)
On the Communication Complexity of Approximate Fixed Points (2016) (20)
Smoothed Analysis of Online and Differentially Private Learning (2020) (20)
Simultaneous Single-Item Auctions (2012) (19)
The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries (2009) (19)
Approximately optimal mechanism design: motivation, examples, and lessons learned (2014) (18)
Equilibrium Efficiency and Price Complexity in Sponsored Search Auctions (2010) (18)
Clean-slate Design for the Internet (2006) (17)
Approximately Optimal Mechanism Design (2018) (17)
Mathematical foundations for social computing (2016) (16)
Online Prediction with Selfish Experts (2017) (15)
Deferred-Acceptance Auctions for Multiple Levels of Service (2017) (15)
Pricing Networks with Selfish Routing (2003) (14)
Pricing Multi-Unit Markets (2017) (14)
Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding (2016) (14)
Do Externalities Degrade GSP ’ s Efficiency ? (2012) (13)
Resource Pools and the CAP Theorem (2020) (13)
Marginals-to-Models Reducibility (2013) (12)
An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization (2018) (12)
Robust Auctions for Revenue via Enhanced Competition (2020) (12)
Tight Error Bounds for Structured Prediction (2014) (12)
The Price of Anarchy in Games of Incomplete Information (2012) (11)
The Complexity of the k-means Method (2016) (10)
Single-Source Stochastic Routing (2006) (10)
Stability and Recovery for Independence Systems (2017) (10)
Automated Market Making and Loss-Versus-Rebalancing (2022) (10)
An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries (2011) (10)
CS168: The Modern Algorithmic Toolbox Lecture #2: Approximate Heavy Hitters and the Count-Min Sketch (2016) (9)
How Does Blockchain Security Dictate Blockchain Implementation? (2021) (9)
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (2015) (9)
Communication Complexity of Discrete Fair Division (2017) (9)
Prior-free auctions with ordered bidders (2012) (9)
Multi-Parameter Mechanism Design (2016) (8)
Worst-Case Efficiency Analysis of Queueing Disciplines (2009) (8)
FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs (2020) (8)
Algorithmic Game Theory: Preface (2007) (7)
Algorithmic Game Theory: Some Greatest Hits and Future Directions (2008) (7)
Metric clustering via consistent labeling (2008) (7)
Distributional Analysis (2020) (7)
When Are Welfare Guarantees Robust? (2016) (6)
Near-optimal multi-unit auctions with ordered bidders (2012) (6)
On Braess ’ s Paradox (2008) (6)
Transaction Fee Mechanism Design (2021) (6)
Complexity Theory, Game Theory, and Economics (2018) (6)
Beyond the Worst-Case Analysis of Algorithms (2019) (6)
Computer/Information Science (2013) (5)
An Optimal Algorithm for Online Unconstrained Submodular Maximization (2018) (5)
Comment on “Computing Correlated Equilibria in Multi-Player Games” (2010) (5)
Why Prices Need Algorithms (2015) (5)
From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation (2021) (5)
Distribution-Free Models of Social Networks (2020) (5)
CS 261 : A Second Course in Algorithms Lecture # 5 : Minimum-Cost Bipartite Matching ∗ (2016) (4)
Guest Editorial Non-Cooperative Behavior in Networking (2007) (4)
Optimal Platform Design (2014) (4)
Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372) (2015) (4)
CS364A: Algorithmic Game Theory Lecture #3: Myerson's Lemma (2013) (3)
Quantifying Loss in Automated Market Makers (2022) (3)
CS 364 A : Algorithmic Game Theory Lecture # 17 : No-Regret Dynamics ∗ (2013) (3)
On a game in directed graphs (2002) (3)
No-Regret Dynamics (2016) (3)
CS 364 A : Algorithmic Game Theory Lecture # 9 : Beyond Quasi-Linearity ∗ (2013) (3)
Myerson's Lemma (2016) (3)
CS364A: Algorithmic Game Theory Lecture #10: Kidney Exchange and Stable Matching (2013) (3)
Money Burning and Implementation (2007) (3)
A General Framework for the Security Analysis of Blockchain Protocols (2020) (3)
Pricing Identical Items (2017) (3)
Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals (2021) (3)
The idemetric property: when most distances are (almost) the same (2018) (3)
CS 269 I : Incentives in Computer Science (2016) (3)
CS264: Beyond Worst-Case Analysis Lecture #15: Smoothed Complexity and Pseudopolynomial-Time Algorithms (2014) (3)
Complexity Theory, Game Theory, and Economics: The Barbados Lectures (2020) (3)
Communication Complexity of Discrete Fair Division (2020) (2)
CS 364 B : Frontiers in Mechanism Design Lecture # 1 : Ascending and Ex Post Incentive Compatible Mechanisms ∗ (2014) (2)
Prior-free multi-unit auctions with ordered bidders (2020) (2)
Resource Augmentation (2020) (2)
ErgasÐa-Episkìphsh dhmosÐeushc : Computing Equilibria in Multi-player Games (2007) (2)
CS168: The Modern Algorithmic Toolbox Lecture #17: Compressive Sensing (2015) (2)
Beyond the Worst-Case Analysis of Algorithms (Introduction) (2020) (2)
CS269I: Incentives in Computer Science Lecture #3: Markets, Everywhere∗ (2018) (2)
CS 269 I : Incentives in Computer Science Lecture # 2 : Stable Matching ∗ (2016) (2)
Counting small cliques in social networks via triangle-preserving decompositions. (2014) (2)
CS168: The Modern Algorithmic Toolbox Lecture #6: Stochastic Gradient Descent and Regularization (2016) (2)
CS369N: Beyond Worst-Case Analysis Lecture #1: Instance Optimality ∗ (2010) (2)
On the Computational Power of Online Gradient Descent (2018) (2)
No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling (2022) (2)
The Price of Anarchy with Polynomial Edge Latency (2001) (2)
CS 364 A : Algorithmic Game Theory Lecture # 5 : Revenue-Maximizing Auctions ∗ (2013) (2)
FPT Algorithms for Finding Near-Cliques in c-Closed Graphs (2020) (2)
CS 269 I : Incentives in Computer Science Lecture # 14 : More on Auctions ∗ (2016) (1)
Over-Provisioning and Atomic Selfish Routing (2016) (1)
Uncoupled potentials for proportional allocation markets (2011) (1)
Public Projects, Boolean Functions, and the Borders of Border’s Theorem (2018) (1)
Algorithmic Mechanism Design (2016) (1)
CS 261 : A Second Course in Algorithms Lecture # 15 : Introduction to Approximation Algorithms ∗ (2016) (1)
CS168: The Modern Algorithmic Toolbox Lecture #13: Sampling and Estimation (2015) (1)
Is Shapley Cost Sharing Optimal ? ∗ ( For the special issue in honor of Lloyd Shapley ) (2016) (1)
Approximately Efficient Two-Sided Combinatorial Auctions (2020) (1)
CS364A: Algorithmic Game Theory Lecture #7: Multi-Parameter Mechanism Design and the VCG Mechanism (2013) (1)
CS 269 I : Incentives in Computer Science Lecture # 15 : The VCG Mechanism ∗ (2016) (1)
CS167: Reading in Algorithms Counting Triangles (2014) (1)
Formalizing Preferences Over Runtime Distributions (2022) (1)
CS364A: Algorithmic Game Theory Lecture #4: Algorithmic Mechanism Design (2013) (1)
CS364A: Algorithmic Game Theory Lecture #8: Combinatorial and Wireless Spectrum Auctions (2013) (1)
Stackelberg Scheduling Strategies ( DRAFT – DO NOT DISTRIBUTE ) (2000) (1)
CS364B: Frontiers in Mechanism Design Lecture #20: Characterization of Revenue-Maximizing Auctions (2014) (1)
Complexity-Theoretic Barriers in Economics (2019) (1)
Lectures on Combinatorial Auctions (2008) (1)
CS168: The Modern Algorithmic Toolbox Lecture #7: Understanding and Using Principal Component Analysis (PCA) (2020) (1)
CS264: Beyond Worst-Case Analysis Lecture #11: LP Decoding (2014) (1)
CS 364 A : Algorithmic Game Theory Lecture # 13 : Potential Games ; A Hierarchy of Equilibria ∗ (2014) (1)
CS364B: Frontiers in Mechanism Design Lecture #17: Part I: Demand Reduction in Multi-Unit Auctions Revisited (2014) (1)
Mathematical Programming Society Newsletter Selfish Routing and the Price of Anarchy 1 MPI 2007 ICCOPT-07 15 74 Selfish Routing and the Price of Anarchy (2007) (1)
CS168: The Modern Algorithmic Toolbox Lecture #3: Similarity Metrics and kd -Trees (2015) (1)
CS364B: Frontiers in Mechanism Design Lecture #3: The Crawford-Knoer Auction (2014) (1)
Complexity-Approximation Trade-offs in Exchange Mechanisms: AMMs vs. LOBs (2023) (1)
CS168: The Modern Algorithmic Toolbox Lecture #10: Tensors, and Low-Rank Tensor Recovery (2015) (1)
Minimizing Regret with Multiple Reserves (2019) (1)
CS 269 I : Incentives in Computer Science Lecture # 18 : Prediction Markets ∗ (2016) (1)
CS 264 : Beyond Worst-Case Analysis Lectures # 9 and 10 : Spectral Algorithms for Planted Bisection and Planted Clique ∗ (2017) (1)
CS264: Beyond Worst-Case Analysis Lecture #8: Exact Recovery in Stable Cut Instances (2014) (1)
Proceedings of the Sixteenth ACM Conference on Economics and Computation (2015) (1)
CS 261 : A Second Course in Algorithms Lecture # 10 : The Minimax Theorem and Algorithms for Linear Programming ∗ (2016) (1)
CS369N: Beyond Worst-Case Analysis Lecture #4: Probabilistic and Semirandom Models for Clustering and Graph Partitioning ∗ (2010) (1)
CS 264 : Beyond Worst-Case Analysis Lecture # 6 : Perturbation-Stable Clustering ∗ (2017) (1)
Pure Nash Equilibria and PLS-Completeness (2016) (1)
Introduction to the Special Issue - Algorithmic Game Theory - STOC/FOCS/SODA 2012 (2016) (1)
CS364A: Algorithmic Game Theory Lecture #18: From External Regret to Swap Regret and the Minimax Theorem (2013) (1)
Complexity ( for Algorithm Designers ) Lecture # 7 : Lower Bounds in Algorithmic Game Theory ∗ (2015) (0)
Special Section on the Fifty-Third IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012) (2015) (0)
Efficiency Guarantees in Large Markets (2016) (0)
CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing (2015) (0)
CS167: Reading in Algorithms Triangle-Dense Graphs (2014) (0)
CS 269 I : Incentives in Computer Science Lecture # 5 : Incentives in Peer-to-Peer Networks ∗ (2016) (0)
CS 168 : The Modern Algorithmic Toolbox Lectures # 17 and # 18 : Spectral Graph Theory (2015) (0)
CS 364 A : Algorithmic Game Theory Lecture # 16 : Best-Response Dynamics ∗ (2014) (0)
Dec . 8 , 2017 Learning in the Presence of Strategic Behavior (0)
Introduction to the Special Issue - Algorithmic Game Theory - STOC/FOCS/SODA 2011 (2015) (0)
Special Section of Games and Economic Behavior dedicated to the 11th and 12th ACM Conference on Electronic Commerce (2015) (0)
Best-Case and Strong Nash Equilibria (2016) (0)
CS364B: Frontiers in Mechanism Design Lecture #4: The Clinching Auction∗ (2014) (0)
CS364B: Frontiers in Mechanism Design Lecture #7: Submodular Valuations (2014) (0)
CS264: Beyond Worst-Case Analysis Lecture #20: From Unknown Input Distributions to (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 19 : Self-Improving Algorithms ∗ (2017) (0)
CS364B: Frontiers in Mechanism Design Lecture #18: Multi-Parameter Revenue-Maximization (2014) (0)
CS 261 : A Second Course in Algorithms Lecture # 12 : Applications of Multiplicative Weights to Games and Linear Programs ∗ (2016) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #4: Boot Camp on Communication Complexity (2015) (0)
Report from Dagstuhl Seminar 13161 Interface of Computation , Game Theory , and Economics (2013) (0)
Book Introduction by the Authors (2017) (0)
Session details: Session 9A (2005) (0)
Network Design with Weighted Players (SPAA 2006 Full Paper Submission) (2006) (0)
CS 261 : A Second Course in Algorithms Lecture # 19 : Beating Brute-Force Search ∗ (2016) (0)
Ignore the Extra Zeroes: Variance-Optimal Mining Pools (2021) (0)
Interactive proofs of proximity: Delegating computation in sublinear time (2013) (0)
CS364B: Frontiers in Mechanism Design Lecture #16: The Price of Anarchy in First-Price Auctions (2014) (0)
Permissionless Consensus (2023) (0)
THREE Qualifying the Inefficiency of Equilibria 439 (2007) (0)
Truthfulness via smoothed complexity (2010) (0)
CS 261 : A Second Course in Algorithms Lecture # 20 : The Maximum Cut Problem and Semidefinite Programming ∗ (2016) (0)
CS168: The Modern Algorithmic Toolbox Lecture #4: Dimensionality Reduction (2015) (0)
CS 168 : The Modern Algorithmic Toolbox Lecture # 19 : Expander Codes (2016) (0)
Swap Regret and the Minimax Theorem (2016) (0)
CS 269 I : Incentives in Computer Science Lecture # 12 : Asymmetric Information and Reputation Systems ∗ (2016) (0)
CS 167 : Reading in Algorithms The Algorithmic Lovász Local Lemma ∗ (2014) (0)
CS168: The Modern Algorithmic Toolbox Lecture #8: How PCA Works (2016) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 5 : Computing Independent Sets : A Parameterized Analysis ∗ (2014) (0)
Title Private Matchings and Allocations (0)
Spectrum Auctions 97 (2016) (0)
Simple Near-Optimal Auctions (2016) (0)
Pricing networks with selfish routing (survey) (2003) (0)
CS 369 N : Beyond Worst-Case Analysis Lecture # 7 : Smoothed Analysis ∗ (2009) (0)
CS 264 : Beyond Worst-Case Analysis Lectures # 11 and 12 : SDP Algorithms for Semi-Random Bisection and Clique ∗ (2017) (0)
Price of Anarchy (2005) (0)
CS364B: Frontiers in Mechanism Design Bonus Lecture: Gross Substitutes and Greedy Algorithms (2014) (0)
Foundations of Blockchains Lectures #7: The Tendermint Protocol (ROUGH DRAFT)∗ (2022) (0)
CS364A: Algorithmic Game Theory Lecture #15: Best-Case and Strong Nash Equilibria (2013) (0)
CS364A: Algorithmic Game Theory Lecture #19: Pure Nash Equilibria and PLS-Completeness (2013) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #5: Lower Bounds for the Extension Complexity of Polytopes (2015) (0)
CS168: The Modern Algorithmic Toolbox Lecture #15 and #16: The Fourier Transform and Convolution (2016) (0)
Kidney Exchange and Stable Matching (2016) (0)
CS167: Reading in Algorithms (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 7 : Exact Recovery in Perturbation-Stable Minimum Cut Instances ∗ (2017) (0)
The Challenges of DSIC Multi-Parameter Mechanism Design (2014) (0)
CS364A: Algorithmic Game Theory Lecture #12: More on Selsh Routing (2013) (0)
CS 269 I : Incentives in Computer Science Lecture # 16 : Revenue-Maximizing Auctions ∗ (2016) (0)
CS 269 I : Incentives in Computer Science Lecture # 10 : Incentives in Crowdsourcing ∗ (2016) (0)
Why prices need algorithms (invited talk) (2017) (0)
Computer/lnformation science (2013) (0)
An interview with Vladimir Trifonov 2005 Danny Lewin best student paper award winner (2005) (0)
CS264: Beyond Worst-Case Analysis Lecture #6: Clustering in Approximation-Stable Instances (2014) (0)
CS 168 : The Modern Algorithmic Toolbox Lecture # 7 : Understanding and Using Principal Component Analysis ( PCA ) (2016) (0)
CS 269 I : Incentives in Computer Science Lecture # 4 : Voting , Machine Learning , and Participatory Democracy ∗ (2016) (0)
CS 261 : A Second Course in Algorithms Lecture # 11 : Online Learning and the Multiplicative Weights Algorithm ∗ (2016) (0)
Building Topic Models Based on Anchor Words (2014) (0)
CS364A: Algorithmic Game Theory Lecture #1: Introduction and Examples ∗ (2013) (0)
CS 364 B : Frontiers in Mechanism Design Lecture # 14 : The Price of Anarchy in Simple Auctions ∗ (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 20 : From Unknown Input Distributions to Instance Optimality ∗ (2014) (0)
CS364A: Algorithmic Game Theory Lecture #20: Mixed Nash Equilibria and PPAD-Completeness (2013) (0)
CS364B: Frontiers in Mechanism Design Lecture #5: The Gross Substitutes Condition (2014) (0)
CS 261 : A Second Course in Algorithms Lecture # 9 : Linear Programming Duality ( Part 2 ) ∗ (2016) (0)
CS364B: Frontiers in Mechanism Design Lecture #19: Interim Rules and Border's Theorem (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 5 : Parameterized Approximation and Running Time Guarantees ∗ (2017) (0)
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers (2023) (0)
CS 364 B : Frontiers in Mechanism Design Lecture # 10 : Coverage Valuations and Convex Rounding ∗ (2014) (0)
CS168: The Modern Algorithmic Toolbox #12: Spectral Graph Theory, Part 2 (2021) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 20 : Application-Specific Algorithm Selection ∗ (2017) (0)
CS364B: Frontiers in Mechanism Design Lecture #15: The Price of Anarchy of Bayes-Nash Equilibria (2014) (0)
CS369N: Beyond Worst-Case Analysis Lecture #2: Models of Data in Online Paging ∗ (2010) (0)
CS264: Beyond Worst-Case Analysis Lecture #2: Instance-Optimal Geometric Algorithms (2014) (0)
CS264: Beyond Worst-Case Analysis Lecture #4: Parameterized Analysis of Online Paging (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 17 : Smoothed Analysis of Local Search ∗ (2017) (0)
Robust Price-of-Anarchy Bounds in Smooth Games (2016) (0)
On a Game in Directed Graphs (Preprint) (2002) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #2: Lower Bounds for One-Way Communication: Disjointness, Index, and Gap-Hamming (2015) (0)
University of Birmingham Sound auction specification and implementation (2015) (0)
Session details: Session 1B (2005) (0)
CS 168 : The Modern Algorithmic Toolbox Lecture # 14 : Markov Chain Monte (2015) (0)
CS364B: Frontiers in Mechanism Design Lecture #6: Gross Substitutes: Welfare Maximization in Polynomial Time (2014) (0)
Spectrum auctions: greed is good… if you do it well! (2015) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 15 : Topic Modeling and Nonnegative Matrix Factorization ∗ (2017) (0)
CS 269 I : Incentives in Computer Science Lecture # 12 : Adverse Selection , Moral Hazard , and Reputation Systems ∗ (2016) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 16 : The Random-Order Model for Online Algorithms ∗ (2017) (0)
CS168: The Modern Algorithmic Toolbox Lecture #14: Markov Chain Monte Carlo (2020) (0)
CS369N: Beyond Worst-Case Analysis Lecture #6: Pseudorandom Data and Universal Hashing (2014) (0)
CS264: Beyond Worst-Case Analysis Lecture #10: Planted and Semi-Random Graph Models (2014) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 9 : A Taste Of Compressive Sensing ∗ (2014) (0)
Revenue-Maximizing Auctions (2016) (0)
APPROXIMATION IN ALGORITHMIC GAME THEORY : ROBUST APPROXIMATION BOUNDS FOR EQUILIBRIA AND AUCTIONS (2011) (0)
CS 364 B : Frontiers in Mechanism Design Lecture # 9 : MIDR Mechanisms via Scaling Algorithms ∗ (2014) (0)
CS369N: Beyond Worst-Case Analysis Lecture #3: Deterministic Planted Models for Clustering and Graph Partitioning ∗ (2010) (0)
Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk (2016) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 18 : Pricing with an Unknown Distribution ∗ (2015) (0)
Approximately Optimal Mechanism Design (Preprint)∗ (2019) (0)
Non-Cooperative Behavior in Networking (Guest Editorial) (2007) (0)
CS 261 : A Second Course in Algorithms Lecture # 18 : Five Essential Tools for the Analysis of Randomized Algorithms ∗ (2016) (0)
CS264: Beyond Worst-Case Analysis Lecture #3: Online Paging and Resource Augmentation ∗ (2014) (0)
CS364A: Algorithmic Game Theory Lecture #2: Mechanism Design Basics (2013) (0)
A Simple Example : First-Price Single-Item Auctions (2017) (0)
CS364A: Algorithmic Game Theory Lecture #6: Simple Near-Optimal Auctions (2013) (0)
CS 364 B : Frontiers in Mechanism Design Lecture # 2 : Unit-Demand Bidders and Walrasian Equilibria ∗ (2014) (0)
Complexity ( for Algorithm Designers ) Lecture # 3 : Lower Bounds for Compressive Sensing ∗ (2015) (0)
CS 269 I : Incentives in Computer Science Lecture # 7 : Selfish Routing and Network Over-Provisioning ∗ (2016) (0)
Introduction (2020) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #1: Data Streams: Algorithms and Lower Bounds (2015) (0)
Equilibria: Definitions, Examples, and Existence (2016) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 20 : Algorithm-Specific Algorithm Selection ∗ (2017) (0)
The Vickrey Auction and Algorithmic Mechanism Design 1 . 1 Auctioning Off a Single Good (2008) (0)
The Top 10 List (2016) (0)
CS 269 I : Incentives in Computer Science Lecture # 6 : Incentivizing Participation ∗ (2016) (0)
Mechanism Design with Payment Constraints 113 (2016) (0)
Hints to Selected Exercises and Problems (2016) (0)
CS 168 : The Modern Algorithmic Toolbox Lecture # 15 : The Fourier Transform and Convolution (2015) (0)
CS 269 I : Incentives in Computer Science Lecture # 13 : Introduction to Auctions ∗ (2016) (0)
CS 364 B : Frontiers in Mechanism Design Lecture # 11 : Undominated Implementations and the Shrinking Auction ∗ (2014) (0)
CS369N: Beyond Worst-Case Analysis Lecture #5: Self-Improving Algorithms ∗ (2010) (0)
CS 269 I : Incentives in Computer Science Lecture # 17 : Scoring Rules and Peer Prediction ( Incentivizing Honest Forecasts and Feedback ) ∗ (2016) (0)
CS 369 N : Beyond Worst-Case Analysis Lecture # 8 : Resource Augmentation ∗ (2009) (0)
CS364B: Frontiers in Mechanism Design Lecture #2: Unit-Demand Bidders and Walrasian (2014) (0)
CS 369 N : Beyond Worst-Case Analysis Lecture # 9 : From Average-Case Analysis to Instance Optimality ∗ Tim Roughgarden † December 4 , 2009 1 Optimal Algorithms and Instance Optimality (2009) (0)
CS264: Beyond Worst-Case Analysis Lecture #14: Smoothed Analysis of Pareto Curves (2014) (0)
CS364B: Frontiers in Mechanism Design Lecture #8: MIR and MIDR Mechanisms (2014) (0)
Introduction and Examples (2016) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #8: Lower Bounds in Property Testing (2015) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 19 : Online Algorithms and Random Permutations ∗ (2015) (0)
Mechanism Design Basics (2016) (0)
CS369E: Communication Complexity (for Algorithm Designers) Lecture #6: Data Structure Lower Bounds (2015) (0)
Mixed Nash Equilibria and PPAD-Completeness (2016) (0)
CS 264 : Beyond Worst-Case Analysis Lecture # 7 : Perturbation Stability and Single-Link + + ∗ (2014) (0)
CS 261 : A Second Course in Algorithms Lecture # 6 : Generalizations of Maximum Flow and Bipartite Matching ∗ (2016) (0)
Strictly Proper Contract Functions Can Be Arbitrage-Free (2021) (0)
CS168: The Modern Algorithmic Toolbox Lecture #14: Linear and Convex Programming, with Applications to Sparse Recovery (2015) (0)
CS364A: Algorithmic Game Theory Lecture #13: Potential Games; A Hierarchy of (2013) (0)
Sharing Costs for Better Selfish Network Design (2006) (0)
CS 269 I : Incentives in (2016) (0)
CS168: The Modern Algorithmic Toolbox Lecture #5: Generalization (Or, How Much Data Is Enough?) (2017) (0)
How Computer Science Informs Modern Auction Design (Invited Talk) (2019) (0)
CS 264 : Beyond Worst-Case Analysis Lectures # 9 and 10 : Spectral Algorithms for Planted Bisection ( a . k . a . Community Detection ) and Planted Clique ∗ (2017) (0)
Communication complexity: (2016) (0)
CS364B: Frontiers in Mechanism Design Lecture #17: Part II: Beyond Smoothness and XOS Valuations (2014) (0)

This paper list is powered by the following services:

Other Resources About Tim Roughgarden

What Schools Are Affiliated With Tim Roughgarden?

Tim Roughgarden is affiliated with the following schools:

Tim Roughgarden's Academic­Influence.com Rankings