Privacy is an essential and often non-negotiable requirement in data analysis and machine learning. In response, the rigorous framework of differential privacy (DP) has emerged as the de facto standard for mitigating privacy concerns. Reflecting its broad impact, there has been a surge of research on differentially private algorithms, with corresponding publications appearing in leading TCS and ML venues.
Within the sublinear algorithm community, an emerging heuristic suggests that sublinear algorithms are inherently well-suited for DP. This follows from DP composition theorems, which stipulate that each data access draws from the limited privacy budget; hence, algorithms minimizing data access, the main property of sublinear approaches, are especially effective in DP settings. Perhaps surprisingly, DP techniques have also inspired the design of non-DP algorithms in several areas, including adversarial robustness, online learning, and dynamic and quantum algorithms.
This workshop will explore connections between DP and other algorithmic disciplines in the following ways:
| 9:00 AM – 9:30 AM | Informal hangout, coffee, breakfast |
|---|---|
| 9:30 AM – 10:00 AM | Brief introductions |
| 10:00 AM – 10:30 AM |
Sofya Raskhodnikova Privately Evaluating Untrusted Black-Box Functions |
| 10:30 AM – 11:00 AM |
Jalaj Upadhyay Chasing the Constant and Its Implications in Private Learning |
| 11:00 AM – 11:30 AM |
Huy Nguyễn Adaptive Power Iteration Method for Differentially Private PCA |
| 11:30 AM – 12:00 PM |
Jelani Nelson TBD |
| 12:00 PM – 2:00 PM | Lunch |
| 2:00 PM – 2:30 PM |
Omri Ben-Eliezer Sublinear Algorithms and Human Recall |
| 2:30 PM – 4:00 PM | Coffee break and poster session |
| 4:00 PM – 5:00 PM | Open problem session |
| 5:00 PM – 6:00 PM | Forming informal groups around common interests; work in groups |
| 6:00 PM | Official end of day (participants can continue working or have dinner together) |
| 9:00 AM – 9:30 AM | Informal hangout, coffee, breakfast |
|---|---|
| 9:30 AM – 10:00 AM |
Gautam Kamath Optimal Differentially Private Sampling of Unbounded Gaussians |
| 10:00 AM – 10:30 AM |
Tal Wagner New Bounds for Kernel Sums via Fast Spherical Embeddings |
| 10:30 AM – 11:00 AM |
Pan Peng A New Private Algorithm for Graph Cuts Approximation |
| 11:00 AM – 1:00 PM | Lunch |
| 1:00 PM – 1:30 PM |
Michael Dinitz Private Matchings: Differential Privacy through Distributed Computing |
| 1:30 PM – 2:00 PM |
Adam Smith TBD |
| 2:00 PM – 2:30 PM | Coffee break |
| 2:30 PM – 4:00 PM | Work in groups |
| 4:00 PM – 5:00 PM | Groups present progress on conjectures, problems, and new thoughts |
| 5:00 PM | Official end of day (likely workshop bonding activity) |
| 9:00 AM – 9:30 AM | Informal hangout, coffee, breakfast |
|---|---|
| 9:30 AM – 10:00 AM |
Samson Zhou Adversarial Robustness on Insertion-Deletion Streams |
| 10:00 AM – 10:30 AM |
Maryam Aliakbarpour Heterogeneity and Privacy in Modern Learning |
| 10:30 AM – 11:00 AM |
Quanquan Liu LAPRAS: Learning-Augmented Private Answering for Linear Query Streams |
| 11:00 AM – 12:00 PM | Final group meetings and end of workshop |
Toyota Technological Institute at Chicago (TTIC). 6045 S Kenwood Ave, Chicago, IL 60637. How to get there.
Here are some nearby hotels, but it is pretty easy to get to TTIC even if you are staying further away:
