I am a PhD student at UT Austin since 2011. My adviser is Adam Klivans . Starting 2015, I am partially supported by the Simons Award for Graduate Students in Theoretical Computer Science.
Earlier, I graduated from IIT Kanpur advised by Surender Baswana .
Email: kothari AT cs.utexas.edu
Research
I am interested in computational complexity, pseudorandomness and computational learning theory.
Papers
Communication with Contextual Uncertainty (with Ilan Komargodski and Madhu Sudan ) Preprint 2015.
Sum of Squares Lower Bounds from Pairwise Independence (with Boaz Barak and Siu On Chan )
STOC 2015 (to appear)
Almost Optimal Pseudorandom Generators for Spherical Caps ( with Raghu Meka )
STOC 2015 (to appear)
Provable Submodular Minimization Using Wolfe's Algorithm (
with Deeparnab Chakrabarty
and Prateek Jain )
NIPS 2014 (Oral Presentation)
Agnostic Learning of Disjunctions on Symmetric Distributions (with Vitaly Feldman )
Arxiv 2014
Embedding Hard Learning Problems in Gaussian Space
(with Adam Klivans ) RANDOM 2014
Nearly Tight Bounds for L_1 Approximating Self Bounding Functions
(with Vitaly Feldman , Jan Vondrak ) Manuscript 2014
Testing Surface Area
(with Ryan O'Donnell , Amir Nayerri and Chengang Wu ) SODA 2014
Learning Coverage Functions and Private Release of Marginals (with Vitaly Feldman ) COLT 2014
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees (with Vitaly Feldman and Jan Vondrak ) COLT 2013
Constructing Hard Functions from Learning Algorithms
(with Adam Klivans and Igor C. Oliveira )
CCC 2013
An Explicit VC-Theorem for Low-Degree Polynomials (with Eshan Chattopadhyay and Adam Klivans ) RANDOM 2012
Differentially Private Online Learning
(with Prateek Jain and Abhradeep Guha Thakurta ) COLT 2012
Submodular Functions are Noise Stable
(with Adam Klivans , Homin K Lee and Mahdi Cheraghchi ) SODA 2012
Undergraduate Research
A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs (with Madan Musuvathi , Sebastian Burckhardt and Santosh Nagarakatte )ASPLOS 2010