Private frequency estimation via projective geometry (and a little bit on K-12 math education)

ABSTRACT
This talk has two parts, on not so closely related topics.

Part 1: Many of us use smartphones and rely on tools like auto-complete and spelling auto-correct to make using these devices more pleasant, but building these tools presents a challenge. On the one hand, the machine-learning algorithms used to provide these features require data to learn from, but on the other hand, who among us is willing to send a carbon copy of all our text messages to device manufacturers to provide that data? “Local differential privacy” (LDP) and related models have become the gold standard for understanding the tradeoffs possible between utility and privacy loss. In this talk we present a new LDP mechanism for estimating data histograms over large numbers of users, making use of projective geometry over finite fields while using a reconstruction algorithm based on dynamic programming.

Part 2: Not by my own choice, but rather by popular request, I will discuss recent developments regarding the California Math Framework, a document put forth by the California Department of Education to provide guidelines for K-12 math education in the state of California. This document, though written for California, is likely to influence K-12 math education across the country. I will discuss the evolution of this document, as well as the essence of the opposition against its first two drafts. A third draft is currently being written, scheduled to be voted on for adoption by the CA State Board of Education in a few months.

The first part of the talk is based on joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple) in ICML 2022.

BIO
Jelani Nelson is a Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley, and also a part-time Research Scientist at Google. His research interests include sketching and streaming algorithms, random projections and their applications to randomized linear algebra and compressed sensing, and differential privacy. He is a recipient of the Presidential Early Career Award for Scientists and Engineers, a Sloan Research Fellowship, and Best Paper Awards at PODS 2010 and 2022. He is also Founder and President of AddisCoder, Inc., which has provided free algorithms training to over 500 Ethiopian high school students since 2011, and co-founder of an offshoot program “JamCoders” in Kingston, Jamaica.