Gautam Kamath Office: Calvin Lab, Room 318 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 April 2018); Google Scholar; DBLP; arXiv; GitHub; Twitter. Feel free to send me comments anonymously here.

About Me

I am 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. I will be joining the University of Waterloo's Cheriton School of Computer Science in July 2019. 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 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.

I was hanging around UC Berkeley in Fall 2015, during the Simons Institute program on Economics and Computation.

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 also spent Summer 2012 working as a Software Engineering Intern on the Platform team for Palantir Gotham, a platform developed by Palantir Technologies.

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

News

• (1/22/19) I will be giving a talk at MIT's Algorithms and Complexity Seminar on February 19, 2019.
• (1/21/19) I will be giving a talk at Berkeley's BLISS Seminar on February 25, 2019.
• (1/14/19) I will be on the PC of SODA 2020.
• (12/19/18) A Chasm Between Identity and Equivalence Testing with Conditional Queries published in Theory of Computing.
• (12/13/18) I will be giving a talk during the Simons Institute Data Privacy Boot Camp on January 29, 2019.
• (12/10/18) I will be giving a talk at Caltech's Mathematics of Information Seminar on January 22, 2019.
• (11/27/18) New paper (The Structure of Optimal Private Tests for Simple Hypotheses) posted to arXiv.
• (11/13/18) One paper (Sever: A Robust Meta-Algorithm for Stochastic Optimization) to be presented at SECML 2018, oral presentation.
• (11/2/18) Video of my talk today on Realizing Robustness is available.
• (10/25/18) I will be giving a talk on Realizing Robustness at the Simons Institute workshop on Robust and High-Dimensional Statistics on November 2.
• (9/27/18) One paper (Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing) accepted to SODA 2019.
• (9/3/18) I was recognized as one of the 30% highest-scoring reviewers for NIPS 2018.
• (8/31/18) My Ph.D. thesis on Modern Challenges in Distribution Testing is complete and submitted! Besides my own work, it should serve as a good survey of recent works in the field.
• (8/22/18) Two papers (1, 2) to be presented at TPDP 2018.
• (8/17/18) I gave a talk at the Workshop on Computational Efficiency and High-Dimensional Robust Statistics. Slides from my talk are available here.
• (7/17/18) New paper (Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing) posted to arXiv.
• (6/19/18) I have been named a Microsoft Research Fellow during my Simons-Berkeley Research Fellowship at the Simons Institute.
• (6/18/18) I successfully defended my PhD thesis! Video of the defense is available here.

Research

Selected Papers (Show all):

The Structure of Optimal Private Tests for Simple Hypotheses.
Clément Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman.
In submission to STOC 2019.


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


Sever: A Robust Meta-Algorithm for Stochastic Optimization.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart.
In submission to ICML 2019.
• Presented at the NIPS 2018 Workshop on Security in Machine Learning (SECML 2018). Oral Presentation.
• Video of a talk by Jerry 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.
Proceedings of the 35th International Conference on Machine Learning (ICML 2018).
• Presented at the 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.
Revise and resubmit to IEEE Transactions on Information Theory.
A preliminary version of this work appeared in the 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).
• 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.
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.
• 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 Canonne, Gautam Kamath.
Theory of Computing, 14(19), 2018.
A preliminary version of this work appeared in the 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 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.

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

• 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 will be on the PC of SODA 2020.
• 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.

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.