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 ]
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.
(with A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin ) Preprint, 2016.
[Video- IAS CS/DM Seminar] [Talk] [Boaz's WOT post]
(with SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four Samuel B. Hopkins and Aaron Potechin )
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 .)
(with Communication with Contextual Uncertainty Badih Ghazi , Ilan Komargodski and Madhu Sudan ) SODA 2016
(with Sum of Squares Lower Bounds from Pairwise Independence Boaz Barak and Siu On Chan )
( with Almost Optimal Pseudorandom Generators for Spherical Caps Raghu Meka )
with Provable Submodular Minimization Using Wolfe's Algorithm Deeparnab Chakrabarty
and Prateek Jain )
NIPS 2014 (Oral Presentation)
(with Agnostic Learning of Disjunctions on Symmetric Distributions Vitaly Feldman )
JMLR, 2015 (to appear)
(with Embedding Hard Learning Problems in Gaussian Space Adam Klivans) RANDOM 2014 [Slides]
(with Nearly Tight Bounds for L_1 Approximating Self Bounding Functions Vitaly Feldman, Jan Vondrak) Manuscript 2014
(with Testing Surface Area Ryan O'Donnell, Amir Nayerri and Chengang Wu) SODA 2014
(with Learning Coverage Functions and Private Release of Marginals Vitaly Feldman)
(with Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees Vitaly Feldman and Jan Vondrak)
COLT 2013 [Slides]
Constructing Hard Functions from Learning Algorithms
(with Adam Klivans and Igor C. Oliveira)
CCC 2013 [Slides]
(with An Explicit VC-Theorem for Low-Degree Polynomials Eshan Chattopadhyay and Adam Klivans ) RANDOM 2012
Differentially Private Online Learning Prateek Jain and Abhradeep Guha Thakurta) COLT 2012
(with Submodular Functions are Noise Stable Adam Klivans, Homin K Lee and Mahdi Cheraghchi) SODA 2012
A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs (with Madan Musuvathi, Sebastian Burckhardt and Santosh Nagarakatte) ASPLOS 2010