Algorithms
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…
Privacy-Friendly Smart Metering
Many smart metering proposals threaten users’ privacy by disclosing fine-grained consumption data to utilities. We have designed protocols that allow for precise billing of consumption while not revealing any consumption information to third parties. We…
Phase Transitions and Computation
The last decade has seen a growing number of connections between statistical physics phase transitions and the theory of computation. Techniques from spin glasses have transformed the understanding of random constraint satisfaction problems while phase…
