Algorithms
Converting any Algorithm into an Incentive-Compatible Mechanism
Does algorithm design become harder in the presence of incentive constraints? The theory of algorithmic mechanism design is largely founded on the presumption that the answer is affirmative, a presumption that has been rigorously confirmed…
PCPs and the Hardness of Generating Private Synthetic Data
We study the computational complexity of differentially private data release for simple, natural queries. Without computational constraints, the work of Blum, Ligett, and Roth (STOC ’08) showed that it is possible to produce differentially private…
The Many Entropies of One-Way Functions
One-way functions are the most basic, unstructured form of cryptographic hardness. Yet in a sequence of celebrated results (mostly in the eighties and early nineties), one-way functions were shown to imply a rich collection of…
Analytical Tools for Natural Algorithms
I will discuss the merits of an algorithmic approach to the analysis of complex self-organizing systems. Specifically, I will show how a new analytical tool, the “total s-energy,” grants us a unique perspective on multiagent…
