
Transaction Fee Mechanism Design
Demand for blockchains such as Bitcoin and Ethereum is far larger than s...
read it

Smoothed Analysis with Adaptive Adversaries
We prove novel algorithmic guarantees for several online problems in the...
read it

From Proper Scoring Rules to MaxMin Optimal Forecast Aggregation
This paper forges a strong connection between two seemingly unrelated fo...
read it

Byzantine Generals in the Permissionless Setting
Consensus protocols have traditionally been studied in a setting where a...
read it

Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP1559
EIP1559 is a proposal to make several tightly coupled additions to Ethe...
read it

A General Framework for the Security Analysis of Blockchain Protocols
Blockchain protocols differ in fundamental ways, including the mechanics...
read it

DistributionFree Models of Social Networks
The structure of largescale social networks has predominantly been arti...
read it

Beyond the WorstCase Analysis of Algorithms (Introduction)
One of the primary goals of the mathematical analysis of algorithms is t...
read it

Distributional Analysis
In distributional or averagecase analysis, the goal is to design an alg...
read it

Resource Augmentation
This chapter introduces resource augmentation, in which the performance ...
read it

FPT Algorithms for Finding Dense Subgraphs in cClosed Graphs
Dense subgraph detection is a fundamental problem in network analysis fo...
read it

Mathematical Foundations for Social Computing
Social computing encompasses the mechanisms through which people interac...
read it

Resource Pools and the CAP Theorem
Blockchain protocols differ in fundamental ways, including the mechanics...
read it

Smoothed Analysis of Online and Differentially Private Learning
Practical and pervasive needs for robustness and privacy in algorithms h...
read it

The Complexity of Contracts
We initiate the study of computing (near)optimal contracts in succinctl...
read it

An Axiomatic Approach to Block Rewards
Proofofwork blockchains reward each miner for one completed block by a...
read it

Approximately Optimal Mechanism Design
Optimal mechanism design enjoys a beautiful and welldeveloped theory, a...
read it

Simple versus Optimal Contracts
We consider the classic principalagent model of contract theory, in whi...
read it

On the Computational Power of Online Gradient Descent
We prove that the evolution of weight vectors in online gradient descent...
read it

Beyond WorstCase Analysis
In the worstcase analysis of algorithms, the overall performance of an ...
read it

An Optimal Algorithm for Online Unconstrained Submodular Maximization
We consider a basic problem at the interface of two fundamental fields: ...
read it

Optimal Algorithms for Continuous Nonmonotone Submodular and DRSubmodular Maximization
In this paper we study the fundamental problems of maximizing a continuo...
read it

The idemetric property: when most distances are (almost) the same
We introduce the idemetric property, which formalises the idea that most...
read it

Finding Cliques in Social Networks: A New DistributionFree Model
We propose a new distributionfree model of social networks. Our definit...
read it

Complexity Theory, Game Theory, and Economics
This document collects the lecture notes from my minicourse "Complexity...
read it

Communication Complexity of Discrete Fair Division
We initiate the study of the communication complexity of fair division w...
read it

The Price of Anarchy in Auctions
This survey outlines a general and modular theory for proving approximat...
read it

Tight Error Bounds for Structured Prediction
Structured prediction tasks in machine learning involve the simultaneous...
read it
Tim Roughgarden
is this you? claim profile
Professor in the Computer Science and Management Science and Engineering Departments at Stanford University.