Thomas Steinke I am a research staff member at IBM Research - Almaden. I completed my PhD in Computer Science at Harvard University, where I was extremely fortunate to be advised by Salil Vadhan. Before that, I was at the University of Canterbury in New Zealand. My research interests include principled approaches to data privacy (specifically, differential privacy), its connections to learning and generalization (particularly in the adaptive setting), and pseudorandomness. For more details, see my CV, research statement, and teaching statement. Email:     Physical: Postal:     650 Harry Road IBM Almaden, B2-412 San Jose, CA 95120

Research

• New Oracle-Efficient Algorithms for Private Synthetic Data Release
  with Giuseppe Vietri, Grace Tian, Mark Bun, and Steven Wu, PriML 2019.
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
  with Mark Bun, NeurIPS 2019.
• Private Hypothesus Selection
  with Mark Bun, Gautam Kamath, and Zhiwei Steven Wu, NeurIPS 2019.
• Towards Instance-Optimal Private Query Release
  with Jaroslaw Blasiok, Mark Bun, and Aleksandar Nikolov, SODA 2019.
• The Limits of Post-Selection Generalization
  with Kobbi Nissim, Adam Smith, Uri Stemmer, and Jonathan Ullman, NIPS 2018.
• Composable and Versatile Privacy via Truncated CDP
  with Mark Bun, Cynthia Dwork, and Guy N. Rothblum, STOC 2018.
• Calibrating Noise to Variance in Adaptive Data Analysis
  with Vitaly Feldman, COLT 2018.
• Tight Lower Bounds for Differentially Private Selection
  with Jonathan Ullman, FOCS 2017.
• Generalization for Adaptively-chosen Estimators via Stable Median
  with Vitaly Feldman, COLT 2017.
• Subgaussian Tail Bounds via Stability Arguments
  with Jonathan Ullman, 2017.
• Upper and Lower Bounds for Privacy and Adaptivity in Algorithmic Data Analysis
  PhD Thesis, Harvard University 2016.
• Exposed! A Survey of Attacks on Private Data
  with Cynthia Dwork, Adam Smith, and Jonathan Ullman, Annual Review of Statistics and Its Application 2017.
• Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
  with Mark Bun, TCC 2016-B.
• Make Up Your Mind: The Price of Online Queries in Differential Privacy
  with Mark Bun and Jonathan Ullman, SODA 2017.
• Robust Traceability from Trace Amounts
  with Cynthia Dwork, Adam Smith, Jonathan Ullman, and Salil Vadhan, FOCS 2015.
• Algorithmic Stability for Adaptive Data Analysis
  with Raef Bassily, Kobbi Nissim, Adam Smith, Uri Stemmer, and Jonathan Ullman, STOC 2016.
• Between Pure and Approximate Differential Privacy
  with Jonathan Ullman, TPDP 2015 & Journal of Privacy and Confidentiality 2017.
• Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
  with Mark Bun, RANDOM 2015.
• Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
  with Jonathan Ullman, COLT 2015.
• Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
  with Salil Vadhan and Andrew Wan, RANDOM 2014 & Theory of Computing 2017.
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
  with Omer Reingold and Salil Vadhan, RANDOM 2013.
• Pseudorandomness for Permuatation Branching Programs Without the Group Theory
  ECCC 2012.
• Learning Hurdles for Sleeping Experts
  with Varun Kanade, ITCS 2012 & Transactions on Computing Theory 2014.
• Hierarchical Heavy Hitters with the Space Saving Algorithm
  with Michael Mitzenmacher and Justin Thaler, ALENEX 2012.
• Constructive Notions of Compactness in Apartness Spaces
  MSc Thesis, University of Canterbury 2011.
• A Rigorous Extension of the Schonhage-Strassen Integer Multiplication Algorithm Using Complex Interval Arithmetic
  with Raazesh Sainudiin, CCA 2010 & Reliable Computing 2013.

Teaching

• 2015 Spring, Harvard University: CS225 Pseudorandomness. Teaching Fellow (Harvard English for Teaching Assistant) for Salil Vadhan.
• 2013 Fall, Harvard University: CS229r Algorithms for Big Data. Teaching Fellow for Jelani Nelson.
• 2012 Fall, Harvard University: CS121 Introduction to the Theory of Computation. Head Teaching Fellow for Salil Vadhan.
• 2013-2016, Lowell House, Harvard University: Non-Resident Tutor.
• 2008-2010, University of Canterbury: Tutor (British/New Zealand English for Teaching Assistant) for six first- and second-year mathematics courses covering linear algebra, calculus, and real analysis.
• 2008-2013, New Zealand Olympiad in Informatics: Tutor at computer science summer camp for high school students.

Olds and News

• I mentored Lydia Zakynthinou as a 2019 summer intern.
• Marco Gaboardi, Jun Sakuma, and I are organizing a workshop on Differential Privacy and its Applications in Japan in mid 2020.
• See here for some open problems in differential privacy, including two from me.
• For Spring 2019, I was visiting the Simons Institute for the Theory of Computing at UC Berkeley for the Data Privacy: Foundations and Applications program.
• Mark Bun, Cynthia Dwork, Toniann Pitassi, Guy Rothblum, Kunal Talwar, and I organized a workshop on the Mathematical Foundations of Data Privacy in April/May 2018 in Banff, Canada.
• Steinke is a german name meaning little stone. The "correct" pronounciation is, approximately, Shteyn-keh, but I sometimes am lazy and use the anglicized pronounciation of Styne-key. I honestly don't care how it is pronounced, as long as it is vaguely recognizable and does not smell bad. My preferred name is Thomas.

Last updated October 2019 by Thomas Steinke.