I am a *final* year 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**

Here's a **[**CV**]**.

** Research **

I am interested in computational complexity, pseudorandomness and learning theory.

**Papers**

*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 (to appear) **

* 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 (to appear). **

*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**