I will first describe negative results for private data analysis via a connection to cryptographic objects called fingerprinting codes. These results show that an (asymptotically) optimal way to solve natural high-dimensional tasks is to decompose them into many simpler tasks. In the second part of the talk, I will discuss concentrated differential privacy, a framework which enables more accurate analyses by precisely capturing how simpler tasks compose.
Bio: Mark Bun is a postdoctoral researcher in the Computer Science Department at Princeton University. He is broadly interested in theoretical computer science, and his research focuses on understanding foundational problems in data privacy through the lens of computational complexity theory. He completed his Ph.D. at Harvard in 2016, where he was advised by Salil Vadhan and supported by an NDSEG Research Fellowship.