I am a 4th year theory PhD student at UT Austin. My adviser is Adam Klivans.
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**

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