Talk by Katrina Ligett (Hebrew University of Jerusalem)

on YouTube ↗37m

" summary

Presents two concrete TCS approaches: a principal–agent model where an agent holds a cost-correlated signal X that the principal neither models nor knows, proves agents prefer revealing features that separate high-cost cases and prefer concealing low-cost cases, and shows simple garbling gives Pareto improvement (agents sometimes share noisy signals, benefiting both sides). The second gives a full characterization of one-run auditing for differential privacy, proves it fails on name-and-shame / all-or-nothing / XOR style algorithms, and shows adaptive guessing strengthens the audit bounds.

AI-written summary · about

" chapters (16)

1. 0:00Avrim Blum's impact and career
2. 1:51Black boxes in ML and TCS reliability
3. 3:18Delegation as principal-agent problem
4. 6:27Regulator's unknown unknowns challenge
5. 8:34Courier payment and agent incentives
6. 10:39Formalizing unknown unknowns
7. 13:52Agent metrics: reveal or conceal
8. 16:41Garbling signals for mutual benefit
9. 19:58Auditing black boxes in sensitive systems
10. 22:13Differential privacy and loss
11. 24:40Privacy auditing: purpose and methods
12. 26:30One-run auditing for efficiency
13. 28:16Limitations of one-run auditing
14. 31:08Strengthening auditing with adaptive guessing
15. 32:32TCS for trustworthy ML systems
16. 33:58Q&A on delegation and incentives

" related talks

• 38mBest of Both World Algorithms from I.I.D. to Adversarial DataJulian Zimmert · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 27mThe ethical algorithmMichael Kearns · AWS Machine Learning Summit 2021
• 26mAaron Roth, Associate Professor, University of Pennsylvania, NYC 2017Aaron Roth · MLconf NYC 2017
• 01h 16mLaw and CSKobbi Nissim · Blockchain in Society: Applications, Economics, Law, and Ethics 2019
• 45mAGT and Machine LearningChristos Papadimitriou · Algorithmic Game Theory and Practice 2015
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 01h 17mTutorial: Privacy, Part IAdam M. Smith, Lydia Zakynthinou · Federated and Collaborative Learning Boot Camp 2026
• 01h 14mTutorial: Privacy, Part IIIAdam M. Smith, Lydia Zakynthinou · Federated and Collaborative Learning Boot Camp 2026