Gautam Kamath Office: DC 3124 Cell: 657-c0mpsci (657-206-7724) 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. Feel free to send me comments anonymously here. I am currently teaching CS 761 - Randomized Algorithms. 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'm mostly interested in principled tools for statistical data science, with a focus on settings which are common in settings of 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

• (11/18/19) New paper (Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning) posted to arXiv.
• (10/16/19) I will be serving as a guest editor for the special issue of TALG for SODA 2020.
• (10/8/19) Shubhankar Mohapatra won one of three $1,000 best poster prizes at University of Waterloo's Cybersecurity and Privacy Institute Annual Conference, presenting on a project with me and Xi He.
• (10/3/19) I will be an area chair for ICML 2020.
• (10/3/19) Clément Canonne and I are organizing a workshop titled "A TCS Quiver" at FOCS 2019.
• (10/1/19) Two posters at PriML 2019, on privately learning graphical models, and testing multivariate distributions.
• (9/9/19) New paper (Differentially Private Algorithms for Learning Mixtures of Separated Gaussians) posted to arXiv.
• (9/3/19) Two papers (Private Hypothesis Selection, Differentially Private Algorithms for Learning Mixtures of Separated Gaussians) accepted to NeurIPS 2019.
• (8/26/19) I will be teaching CS 761 - Randomized Algorithms in Fall 2019.
• (8/22/19) Robust Estimators in High Dimensions without the Computational Intractability was invited to Communications of the ACM as a Research Highlight.
• (8/10/19) Two posters at TPDP 2019 (on privately learning graphical models, and testing multivariate distributions), and one oral presentation (Private Hypothesis Selection).
• (8/7/19) I will be on the program committee of ICALP 2020.
• (8/2/19) I will be on the program committee of PriML 2019, a workshop at NeurIPS 2019.
• (7/13/19) I will be giving a talk at NTUA's Corelab Seminar on July 18.
• (7/9/19) Testing Ising Models accepted to IEEE Transactions on Information Theory.
• (7/2/19) I will be attending and organizing a session at WALE 2019.
• (7/1/19) I started as an Assistant Professor at University of Waterloo.
• (6/17/19) I started a blog.

Research

Selected Papers (Show all)

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 STOC 2020.
• ECCC link.


Privately Learning Markov Random Fields.
Gautam Kamath, Janardhan Kulkarni, Zhiwei Steven Wu, Huanyu Zhang.
Manuscript.
• 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 Identity Testing for High-Dimensional Distributions.
Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou.
In submission to STOC 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.


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.
In submission to the Journal of Privacy and Confidentiality (invited to the special issue for TPDP 2018).
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.
To appear in IEEE Transactions on Information Theory.
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

• 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

• 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 (or will be) on the program committee of the following theory conferences: SODA 2020, ICALP 2020.
• I have (or will be) an area chair for the following machine learning conferences: ICML 2020.
• I have (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.
• 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 761 - Randomized Algorithms: Fall 2019

Advising

• Sourav Biswas (Undergraduate Student, Fall 2019)
• Pranav Subramani (Undergraduate Student, Fall 2019)
• Vikrant Singhal (Visiting Ph.D. Student, Fall 2019)

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.