I am a final year PhD candidate at UT Austin since 2011. I am visiting Harvard University in Spring/Summer 2016 and and located in MD 138.
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].


I am interested in computational complexity especially in understanding the strength of generic algorithmic schemes based on linear and semidefinite programming. I am also interested in pseudorandomness and learning theory.


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 )

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)