research
∙
07/04/2023
Transaction Fee Mechanism Design with Active Block Producers
The incentive-compatibility properties of blockchain transaction fee mec...
share
research
∙
06/29/2023
When Bidders Are DAOs
In a typical decentralized autonomous organization (DAO), people organiz...
research
∙
04/28/2023
Permissionless Consensus
Blockchain protocols typically aspire to run in the permissionless setti...
research
∙
03/01/2023
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers
In decentralized finance ("DeFi"), automated market makers (AMMs) enable...
research
∙
02/22/2023
Complexity-Approximation Trade-offs in Exchange Mechanisms: AMMs vs. LOBs
This paper presents a general framework for the design and analysis of e...
research
∙
05/25/2022
Formalizing Preferences Over Runtime Distributions
When trying to solve a computational problem we are often faced with a c...
research
∙
02/22/2022
No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling
For each of T time steps, m experts report probability distributions ove...
research
∙
11/04/2021
Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals
The problem of aggregating expert forecasts is ubiquitous in fields as w...
research
∙
09/10/2021
How Does Blockchain Security Dictate Blockchain Implementation?
Blockchain protocols come with a variety of security guarantees. For exa...
research
∙
09/03/2021
Strictly Proper Contract Functions Can Be Arbitrage-Free
We consider mechanisms for truthfully eliciting probabilistic prediction...
research
∙
06/02/2021
Transaction Fee Mechanism Design
Demand for blockchains such as Bitcoin and Ethereum is far larger than s...
research
∙
02/16/2021
Smoothed Analysis with Adaptive Adversaries
We prove novel algorithmic guarantees for several online problems in the...
research
∙
02/14/2021
From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation
This paper forges a strong connection between two seemingly unrelated fo...
research
∙
01/18/2021
Byzantine Generals in the Permissionless Setting
Consensus protocols have traditionally been studied in a setting where a...
research
∙
12/01/2020
Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559
EIP-1559 is a proposal to make several tightly coupled additions to Ethe...
research
∙
09/20/2020
A General Framework for the Security Analysis of Blockchain Protocols
Blockchain protocols differ in fundamental ways, including the mechanics...
research
∙
07/30/2020
Distribution-Free Models of Social Networks
The structure of large-scale social networks has predominantly been arti...
research
∙
07/26/2020
Beyond the Worst-Case Analysis of Algorithms (Introduction)
One of the primary goals of the mathematical analysis of algorithms is t...
research
∙
07/26/2020
Distributional Analysis
In distributional or average-case analysis, the goal is to design an alg...
research
∙
07/26/2020
Resource Augmentation
This chapter introduces resource augmentation, in which the performance ...
research
∙
07/19/2020
FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs
Dense subgraph detection is a fundamental problem in network analysis fo...
research
∙
07/07/2020
Mathematical Foundations for Social Computing
Social computing encompasses the mechanisms through which people interac...
research
∙
06/18/2020
Resource Pools and the CAP Theorem
Blockchain protocols differ in fundamental ways, including the mechanics...
research
∙
06/17/2020
Smoothed Analysis of Online and Differentially Private Learning
Practical and pervasive needs for robustness and privacy in algorithms h...
research
∙
02/27/2020
The Complexity of Contracts
We initiate the study of computing (near-)optimal contracts in succinctl...
research
∙
09/23/2019
An Axiomatic Approach to Block Rewards
Proof-of-work blockchains reward each miner for one completed block by a...
research
∙
12/31/2018
Approximately Optimal Mechanism Design
Optimal mechanism design enjoys a beautiful and well-developed theory, a...
research
∙
08/10/2018
Simple versus Optimal Contracts
We consider the classic principal-agent model of contract theory, in whi...
research
∙
07/03/2018
On the Computational Power of Online Gradient Descent
We prove that the evolution of weight vectors in online gradient descent...
research
∙
06/26/2018
Beyond Worst-Case Analysis
In the worst-case analysis of algorithms, the overall performance of an ...
research
∙
06/08/2018
An Optimal Algorithm for Online Unconstrained Submodular Maximization
We consider a basic problem at the interface of two fundamental fields: ...
research
∙
05/24/2018
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
In this paper we study the fundamental problems of maximizing a continuo...
research
∙
04/30/2018
The idemetric property: when most distances are (almost) the same
We introduce the idemetric property, which formalises the idea that most...
research
∙
04/20/2018
Finding Cliques in Social Networks: A New Distribution-Free Model
We propose a new distribution-free model of social networks. Our definit...
research
∙
01/02/2018
Complexity Theory, Game Theory, and Economics
This document collects the lecture notes from my mini-course "Complexity...
research
∙
11/11/2017
Communication Complexity of Discrete Fair Division
We initiate the study of the communication complexity of fair division w...
research
∙
07/26/2016
The Price of Anarchy in Auctions
This survey outlines a general and modular theory for proving approximat...
research
∙
09/19/2014