Abstract: We will discuss classic and new results that use error-correcting codes to prove lower bounds on the privacy-utility tradeoffs of differentially private mechanisms. The existence of such codes has been used to show the hardness of privately estimating simple counting queries. Typically, the lower bounds are proven via packing-style arguments and the use of fingerprinting codes. New results extend such arguments, from the simple counting query settings over a finite domain, to situations where the data might be drawn from an infinite (but structured) domain.
Bio: Daniel Alabi is an assistant professor in the Electrical and Computer Engineering department at the University of Illinois at Urbana-Champaign (UIUC). Until June 2025, Daniel was a postdoctoral researcher at Columbia University and a junior fellow in the Simons Foundation Society of Fellows. He received his S.M. and Ph.D. degrees from Harvard University. In 2022, he led the founding of NaijaCoder Inc, a non-profit that aims to proliferate early algorithms education in Africa with a focus on Nigeria. (We host annual summer camps in different states within Nigeria and would like to involve UIUC students too.) Daniel's current research interests are primarily in information theory and security. This semester, he is teaching a course centered on information-theoretic security.