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 June 2015); Google Scholar; DBLP; arXiv

About Me

I'm a fourth year Ph.D student 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 a research intern at Microsoft Research Cambridge in Summer 2015, working with Milan Vojnovic and Prateek Jain.

I am visiting 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.

Research

Selected Papers (Show all):

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


Testing Independence of Ising Models via Exchangeable Pairs.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
In preparation, 2016.


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


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

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

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