Gautam Kamath Office: DC 3124 (currently empty) Cell: 657-c0mpsci (657-206-7724) (currently inactive) Email: ?@csail.mit.edu, but replace ? with the first letter of my first name Links to: CV (as of October 2019); Google Scholar; DBLP; arXiv; GitHub; Twitter; Blog. My lab is The Salon. Feel free to send me comments anonymously here. Note that, by design, I won't be able to respond -- if you need me to, it's better handled via email, or leaving some way for me to reply. I am unable to respond to requests for internships or graduate admission applications from outside the university. If you do feel compelled to contact me in this way, I am far more likely to remember you if you demonstrate that you have genuinely engaged with my work. Instead, I recommend that you apply for graduate studies through the standard channels.

About Me

I am an Assistant Professor at the University of Waterloo's Cheriton School of Computer Science. I lead The Salon. I'm mostly interested in principled methods for statistics and machine learning, with a focus on settings which are common in modern data analysis (high-dimensions, robustness, and privacy).

I was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing for the Fall 2018 semester program on Foundations of Data Science and the Spring 2019 semester program on Data Privacy: Foundations and Applications. Before that, I completed my Ph.D. at MIT, affiliated with the Theory of Computing group in CSAIL. I was very fortunate to be advised by Costis Daskalakis.

Before MIT, I spent four wonderful years at Cornell University, graduating in May 2012 with a degree in Computer Science and Electrical and Computer Engineering. At Cornell, I was incredibly lucky to have the opportunity to work with Bobby Kleinberg.

I really enjoy giving talks and communicating my work! Please don't hesitate to ask if you'd like to hear about it.

News

• (8/10/20) My lab, The Salon, has a website!.
• (8/10/20) I recorded a talk on CoinPress. I gave a similar talk at JSM 2020 and the Harvard Privacy Tools group meeting.
• (8/9/20) Five papers (1, 2, 3, 4, 5) will be presented at the workshop TPDP 2020.
• (7/18/20) We launched DifferentialPrivacy.org!
• (7/12/20) I have been awarded an NSERC Discovery Grant, including an Accelerator Supplement. See these articles for some more details.
• (7/12/20) I will be a reader of Kaiwen Wu's Master's Thesis.
• (7/10/20) I will be a reader of Beracira Chen's Master's Thesis.
• (7/9/20) I will be an area chair for ICLR 2021.
• (6/30/20) We wrote a "Behind the Screens" look at STOC 2020, a document which may be useful to other virtual conference organizers.
• (6/18/20) I will be on the program committee for ALT 2021.
• (6/15/20) I will be on the program committee for TPDP 2020.
• (6/11/20) New paper on arXiv: CoinPress: Practical Private Mean and Covariance Estimation. Code is available here.
• (5/31/20) One paper accepted to ICML 2020.
• (5/29/20) I will serve on Vikrant Singhal's thesis committee.
• (5/25/20) Two papers (1, 2) accepted to COLT 2020.
• (5/13/20) I gave a talk on robustness at Waterloo's Algorithms and Complexity seminar.
• (5/11/20) I will be a reader of Amur Ghose's Master's Thesis.
• (5/9/20) I will be a reader of Shubhankar Mohapatra's Master's thesis.
• (5/5/20) I am now a general co-chair for STOC 2020, helping out with the transition to a virtual conference.
• (4/17/20) Jonathan Ullman and I wrote a brief survey of differentially private statistics: A Primer on Private Statistics.
• (4/1/20) New paper on arXiv: The Discrete Gaussian for Differential Privacy. Code available here.
• (3/9/20) Xi He and I were awarded a 2020 Resources from Research Groups grant from Compute Canada. Thank you Compute Canada!
• (3/7/20) I was recognized as one of six top instructors for graduate courses in Computer Science in Fall 2019 (for CS 761).
• (2/27/20) New paper on arXiv: PAPRIKA: Private Online False Discovery Rate Control. Code is available here.
• (2/25/20) INSPECTRE: Privately Estimating the Unseen accepted to the Journal of Privacy and Confidentiality, Special Issue for TPDP 2018.
• (2/25/20) I will be speaking in a session on differential privacy (organized by Weijie Su) at the 2020 Joint Statistical Meetings.
• (02/23/20) Three new papers on arXiv! All on differential privacy, and include learning MRFs, mean estimation for heavy-tailed distributions, and hypothesis selection (in the local model).
• (2/10/20) I will serve on Amit Levi's thesis committee.
• (1/23/20) I will be on the program committee of Random 2020.
• (1/7/20) I will be organizing a session at ITA 2020.
• (1/3/20) I will be a reader of Sachin Vernekar's Master's thesis.
• (1/2/20) I will be a reader of Sushant Agarwal's Master's thesis.

Research

Selected Papers (Show all)

CoinPress: Practical Private Mean and Covariance Estimation.
Sourav Biswas, Yihe Dong, Gautam Kamath, Jonathan Ullman.
In submission to NeurIPS 2020.
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Video of a talk is available here.
• Code is available here.


The Discrete Gaussian for Differential Privacy.
Clément L. Canonne, Gautam Kamath, Thomas Steinke.
In submission to NeurIPS 2020.
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Code is available here.


Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten.
In submission to SODA 2021.
• ECCC link.
• Featured in: Property Testing Review.
• Talk by Erik here.


Private Identity Testing for High-Dimensional Distributions.
Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou.
In submission to NeurIPS 2020.
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019).
• Presented at the NeurIPS 2019 Workshop on Privacy in Machine Learning (PriML 2019).
• Featured in: Property Testing Review.


PAPRIKA: Private Online False Discovery Rate Control.
Wanrong Zhang, Gautam Kamath*, Rachel Cummings*. (Contribution order)
In submission to NeurIPS 2020.
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Code is available here.


Privately Learning Markov Random Fields.
Huanyu Zhang, Gautam Kamath*, Janardhan Kulkarni*, Zhiwei Steven Wu*. (Contribution order)
Proceedings of the 37th International Conference on Machine Learning (ICML 2020).
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019).
• Presented at the NeurIPS 2019 Workshop on Privacy in Machine Learning (PriML 2019).


Private Mean Estimation of Heavy-Tailed Distributions.
Gautam Kamath, Vikrant Singhal, Jonathan Ullman.
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• COLT talk by Vikrant available here.


Locally Private Hypothesis Selection.
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang.
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Featured in: Property Testing Review.
• COLT talk by Janardhan available here.


Differentially Private Algorithms for Learning Mixtures of Separated Gaussians.
Gautam Kamath, Or Sheffet, Vikrant Singhal, Jonathan Ullman.
Advances in Neural Information Processing Systems 32 (NeurIPS 2019).


Private Hypothesis Selection.
Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu.
Advances in Neural Information Processing Systems 32 (NeurIPS 2019).
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019). Oral Presentation.
• Video of a talk by Mark is available here.


Sever: A Robust Meta-Algorithm for Stochastic Optimization.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart.
Proceedings of the 36th International Conference on Machine Learning (ICML 2019).
• Presented at the NeurIPS 2018 Workshop on Security in Machine Learning (SECML 2018). Oral Presentation.
• Code is available here.
• Video of a talk by Jerry is available here.


Privately Learning High-Dimensional Distributions.
Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman.
Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019).
• Presented at the 2018 Workshop on Theory and Practice of Differential Privacy (TPDP 2018).
• Video of a talk by Jon is available here.


The Structure of Optimal Private Tests for Simple Hypotheses.
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman.
Proceedings of the 51st ACM Symposium on Theory of Computing (STOC 2019).
• Video of a talk by Audra is available here.


Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing.
Gautam Kamath, Christos Tzamos.
Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
• ECCC link.
• Slides from my talk at SODA available here.
• Featured in: Property Testing Review.


INSPECTRE: Privately Estimating the Unseen.
Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang.
Journal of Privacy and Confidentiality (special issue for TPDP 2018), to appear.
Proceedings of the 35th International Conference on Machine Learning (ICML 2018).
• Presented at the CCS 2018 Workshop on Theory and Practice of Differential Privacy (TPDP 2018).
• Code is available here.
• Featured in: Property Testing Review
• Video of a talk by Huanyu is available here.


Actively Avoiding Nonsense in Generative Models.
Steve Hanneke, Adam Kalai, Gautam Kamath, Christos Tzamos.
Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018).
• Video of Adam's talk at COLT can be viewed here.


Which Distribution Distances are Sublinearly Testable?
Constantinos Daskalakis, Gautam Kamath, John Wright.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
• ECCC link.
• Featured in: Property Testing Review.


Testing Ising Models.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
IEEE Transactions on Information Theory, 65(11), 2019.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
• ECCC link.
• Featured in: Property Testing Review.


Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).


Concentration of Multilinear Functions of the Ising Model with Applications to Network Data.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
Advances in Neural Information Processing Systems 30 (NIPS 2017).
• Code is available here.
• A three-minute summary video for NIPS is available here.
• Our NIPS poster is viewable here.


Priv'IT: Private and Sample Efficient Identity Testing.
Bryan Cai, Constantinos Daskalakis, Gautam Kamath.
Proceedings of the 34th International Conference on Machine Learning (ICML 2017).
• Presented at the ICML 2017 Workshop on Private and Secure Machine Learning 2017 (PSML 2017). Oral Presentation.
• Video of my talk at ICML can be viewed here.
• Code is available here.
• Featured in: Property Testing Review.


Being Robust (in High Dimensions) Can Be Practical.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
Proceedings of the 34th International Conference on Machine Learning (ICML 2017).
• Code is available here.
• Video of Jerry's talk at ICML can be viewed here.


Robust Estimators in High Dimensions without the Computational Intractability.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
SIAM Journal on Computing, 48(2), 2019. Special Issue for FOCS 2016.
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
• Invited to the SIAM Journal on Computing Special Issue for FOCS 2016.
• Invited to Highlights of Algorithms 2017.
• Invited to Communications of the ACM, Research Highlights.
• Video of Jerry's talk at FOCS can be viewed here. Video of Jerry's talk at TCS+ can be viewed here. Video of Ankur's talk at the Simons Institute can be viewed here.
• Featured in: MIT News, USC Viterbi News


A Size-Free CLT for Poisson Multinomials and its Applications.
Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos.
Proceedings of the 48th ACM Symposium on Theory of Computing (STOC 2016).


Optimal Testing for Properties of Distributions.
Jayadev Acharya, Constantinos Daskalakis, Gautam Kamath.
Advances in Neural Information Processing Systems 28 (NIPS 2015).
• Selected for a Spotlight Presentation (4.5% acceptance rate).
• Video of a talk by Costis at UT Austin can be viewed here. Video of the spotlight talk by Jayadev at NIPS can be viewed here (at 9:15).
• Featured in: MIT Theory of Computation Student Blog, Property Testing Review.
• An extremely condensed version of this paper appeared in Volume Four of Tiny Transactions on Computer Science (Tiny ToCS).


On the Structure, Covering, and Learning of Poisson Multinomial Distributions.
Constantinos Daskalakis, Gautam Kamath, Christos Tzamos.
Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).
• Video of the talk by Christos at FOCS can be viewed here.


A Chasm Between Identity and Equivalence Testing with Conditional Queries.
Jayadev Acharya, Clément L. Canonne, Gautam Kamath.
Theory of Computing, 14(19), 2018.
Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM 2015).
• ECCC link.
• Slides from Clément's talk at RANDOM available here.
• Featured in: Oded Goldreich's Choices, Property Testing Review, Sublinear.info.


Adaptive Estimation in Weighted Group Testing.
Jayadev Acharya, Clément L. Canonne, Gautam Kamath.
Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT 2015).


Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians.
Constantinos Daskalakis, Gautam Kamath.
Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014).
• Slides from the talk at COLT available here. Video of the talk can be viewed here.


An Analysis of One-Dimensional Schelling Segregation.
Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg.
Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012).
• I was very lucky to be awarded the inaugural STOC Best Student Presentation Award by SIGACT for this talk.
• Slides from the talk at STOC available here, adapted from slides from a talk by Nicole at MSR. Video of the talk can be viewed here.
• Featured in: American Scientist.

Workshop Papers (Show)

Theses

• Modern Challenges in Distribution Testing.
  Gautam Kamath.
  Ph.D. Thesis, 2018.
• On Learning and Covering Structured Distributions.
  Gautam Kamath.
  M.Sc. Thesis, 2014.

Talk Videos

• CoinPress: Practical Private Mean and Covariance Estimation.
• Privately Learning High-Dimensional Distributions. Presented at Data Privacy: From Foundations to Applications.
• Private Statistics: A TCS Perspective. Presented as part of the mini-course on private statistics at the Data Privacy Boot Camp.
• Realizing Robustness. Presented at the Robust and High-Dimensional Statistics Workshop.
• Modern Challenges in Distribution Testing. My PhD defense talk.
• Differentially Private Hypothesis Testing and Property Estimation. Presented at Mathematical Foundations of Data Privacy.
• Robustness in Unsupervised and Supervised Learning. Presented at Modern Challenges of Learning Theory.
• Testing with Alternative Distances. Presented at Frontiers of Distribution Testing workshop at FOCS 2017.
• Priv'IT: Private and Sample Efficient Identity Testing. Presented at ICML 2017.
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians. Presented at COLT 2014.
• An Analysis of One-Dimensional Schelling Segregation. Presented at STOC 2012.

Coauthors

Other Writings

• We wrote a "Behind the Screens" look at STOC 2020, a document which may be useful to other virtual conference organizers. With Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, and input from Julia Chuzhoy.
• Jonathan Ullman and I wrote a brief survey of differentially private statistics: A Primer on Private Statistics.
• For Advanced Algorithms (6.854), I wrote a survey of matroid secretary problem algorithms as a final project.
• Some bounds on the expectation of the maximum of samples from a Gaussian. I thought this was a fairly natural problem, but when I wrote it, I was unable to find anyone else who had computed the explicit lower bound here.

Service

• I have been (or will be) a general chair for the following conferences: STOC 2020.
• I have been (or will be) on the program committee of the following theory conferences: SODA 2020, ICALP 2020, Random 2020.
• I have been (or will be) an area chair (or core program committee member) for the following machine learning conferences: ICML 2020, ALT 2021, ICLR 2021.
• I have been (or will be) on the program committee (i.e., a reviewer) of the following machine learning conferences: NIPS 2016, ICML 2018, NeurIPS 2018, AISTATS 2019, ICML 2019, NeurIPS 2019, AAAI 2020, AISTATS 2020.
• I have (or will be) on the program committee of the following workshops: TPDP 2019, PriML 2019, TPDP 2020.
• I am a maintainer of the CS Theory Blog Aggregator, along with Arnab Bhattacharyya and Suresh Venkatasubramanian.
• Clément Canonne and I organized a workshop called "A TCS Quiver" at FOCS 2019.
• Clément Canonne and I organized a workshop on distribution testing at FOCS 2017.
• Clément Canonne and I organized a workshop on orthogonal polynomials at FOCS 2016.
• I'm an editor for the MIT Theory of Computation Student Blog and Property Testing Review.
• I'm one of the organizers of TCS+, an online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.
• I organized the second Sublinear Day, which was on April 10, 2015 at MIT.
• I was the head organizer for the Second Annual Danny Lewin MIT Theory Student Retreat, which took place in October 2013. Aloni and Themis wrote a bit about this retreat here.
• From Fall 2012 to Fall 2013, I was in charge of the Theory Group lunch, which was the current incarnation of Great Ideas in Theoretical Computer Science at CSAIL. The website for the current offering is here.

Other Projects

• As a final project for a microcontrollers class, my partner Dominick Grochowina and I made an automated vocalist for the game Rock Band. This was featured on the website Hack A Day. Videos of the bot in action can be seen here and here.
• I worked on a project called Plannit, which won second place at Cornell Facebook Hackathon. Partners on this project were Jasdeep Hundal, Sohan Jain, and Harry Terkelsen.

Teaching

• CS 240 - Data Structures and Data Management: Spring 2020
• CS 761 - Randomized Algorithms: Fall 2019

Advising

• Sourav Biswas (Undergraduate Student, Fall 2019 - Present)
• Christian Covington (Master's Student, starting ???)
• Mahbod Majid (Master's Student, starting ???)
• Argyris Mouzakis (PhD Student, starting ???)
• Vikrant Singhal (Visiting Ph.D. Student, Fall 2019)
• Pranav Subramani (Undergraduate Student, Fall 2019 - Present)

Resources

• TCS+: An series of online seminars in theoretical computer science.
• Simons Institute Videos: Videos from workshops hosted at the Simons Institute for the Theory of Computing.
• BIRS Videos: Videos from workshops hosted at the Banff International Research Station.
• Institute for Advanced Studies Videos: Videos from the IAS. Note that many are related to other fields besides computer science.
• Microsoft Research Talks: Talks at Microsoft Research, including a variety of topics beyond theory.
• Shannon Channel: A series of online seminars in information theory.
• Princeton TCS Videos: Videos from theory lunch and workshops within Princeton's theory group.
• Techtalks.tv: Talks from a number of conferences. You may have to search for the conferences of interest. Some may include FOCS and ICML.
• Videolectures.net: Lecture videos from a number of conferences and workshops, seems to be primarily focused on machine learning events.

Other

• I used to go by the name "G", though I now prefer Gautam. Also, my name is not Guatam Kamath, though it is commonly misspelled as such.
• My friends Aviv Adler, Greg Bodwin, and primarily Jennifer Tang, made a small puzzle hunt for my graduation. You can check out the puzzles here: 1, 2, 3, 4, 5, 6. Warning that they can be incredibly unfair if you are not me, but oh well. Try them out!