I am a final year PhD candidate 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 . Here's a [ CV] .
Research
I am interested in computational complexity - specifically in understanding the strength of generic algorithmic schemes based on linear and semidefinite programming. I am also interested in pseudorandomness and learning theory.
Papers
A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique (with Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin ) Preprint, 2016.
[Video- IAS CS/DM Seminar] [Talk] [Boaz's WOT post]
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four (with Samuel B. Hopkins and Aaron Potechin )
SODA 2016
Invited to the ACM Transactions on Algorithms, Special Issue for SODA 2016
(Conference version to be merged with
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program by Tselil Schramm and Prasad Raghavendra .)
Communication with Contextual Uncertainty (with Badih Ghazi , Ilan Komargodski and Madhu Sudan ) SODA 2016
Sum of Squares Lower Bounds from Pairwise Independence (with Boaz Barak and Siu On Chan )
STOC 2015 [Slides]
Almost Optimal Pseudorandom Generators for Spherical Caps ( with Raghu Meka )
STOC 2015 [Slides]
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 )
JMLR, 2015 (to appear)
Embedding Hard Learning Problems in Gaussian Space
(with Adam Klivans ) RANDOM 2014 [Slides]
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 [Slides]
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees (with Vitaly Feldman and Jan Vondrak )
COLT 2013 [Slides]
Constructing Hard Functions from Learning Algorithms
(with Adam Klivans and Igor C. Oliveira )
CCC 2013 [Slides]
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 [Slides]
Undergraduate Research
A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs (with Madan Musuvathi , Sebastian Burckhardt and Santosh Nagarakatte )ASPLOS 2010