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…
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…
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…
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…
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…
