**Postdoctoral F
ellow, Center for Research on Computation and Society, Harvard University**

**"Privacy and the Complexity of Simple Queries"**

*
Abstract: The goal of differentially private data analysis
is to design algorithms for analyzing datasets while ensuring that sensiti
ve information about individuals is not revealed. In this talk I will prese
nt both new lower bounds and new algorithms for differentially private data
analysis. On the negative side, I will present some new, nearly-optimal lo
wer bounds on the amount of data required to release differentially private
statistics on high-dimensional datasets. These results show that there is
a significant "price of differential privacy" in high-dimensional datasets.
We prove these lower bounds using a cryptographic primitive called a finge
rprinting code that we show is closely connected to differentially private
data analysis. On the positive side, I will present efficient algorithms fo
r computing differentially private contingency tables, using techniques fro
m computational learning theory.*

**Bio: ***Dr. *
Jonathan Ullman is a postdoctoral fellow at the Center for Research on
Computation and Society at Harvard University. He recently completed his Ph
.D., also at Harvard, where he was advised by Salil Vadhan and was a Siebel
Scholar. He is interested in the foundations of data privacy and its conne
ctions to other areas of theoretical computer science such as cryptography,
learning theory, and game theory..

*Hosted by: EECS*