Gautam "G" Kamath Office: MIT CSAIL, 32-G628 Cell: 657-c0mpsci (657-206-7724) Email: ?@csail.mit.edu, but replace ? with the letter in quotation marks in my name above Links to: CV (as of October 2017); Google Scholar; DBLP; arXiv

About Me

I'm a final year Ph.D student (graduating June 2018) at MIT, affiliated with the Theory of Computing group at CSAIL. I am very fortunate to be advised by Costis Daskalakis. My primary research interests are learning theory and applied probability.

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

• (9/29/17) Three papers (1, 2, and 3) accepted to SODA 2018.
• (9/26/17) I will be giving a talk at Cornell Theory Tea on September 28, 2017.
• (9/20/17) I will be giving a talk at the McMaster University Computing and Software Department Seminar on October 5, 2017.
• (9/14/17) I will be giving a talk at the MIT Theory Lunch on October 26, 2017.
• (9/14/17) I will be be giving a talk on distribution testing at the UMass Amherst Theory Seminar on October 24, 2017.
• (9/7/17) Clément Canonne and I are organizing a workshop on frontiers in distribution testing at FOCS 2017, on October 14, 2017.
• (9/4/17) One paper (Concentration of Multilinear Functions of the Ising Model with Applications to Network Data) accepted to NIPS 2017.
• (8/1/17) I will be be giving a talk on distribution testing at the Cornell Theory Seminar on September 25, 2017.

Research

Selected Papers (Show all):

ANACONDA: A Non-Adaptive Conditional Sampling Algorithm for Equivalence Testing.
Gautam Kamath, Christos Tzamos.
In preparation.


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).
• Featured in: Property Testing Review.


Testing Ising Models.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
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).


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).
• 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).


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.
Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM 2015).
In submission to Theory of Computing.
• 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.

Coauthors

Other Writings

• My Master's thesis was titled On Learning and Covering Structured Distributions.
• 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 I was unable to find anyone else who had computed the explicit lower bound 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.

Random Stuff

• Clément Canonne and I are organizing 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.
• My name is not Guatam Kamath, though it is commonly misspelled as such.