I am a Research Instructor in the Department of Computer Science at Princeton University and a member of the School of Mathematics at the Institute for Advanced Study. I am also a part of the Simons Algorithms and Geometry Collaboration . I am thankful to the Schmidt foundation for funding my position.
Previously, I received my PhD from UT Austin advised by Adam Klivans, where I was partially supported by the Simons Award for Graduate Students in Theoretical Computer Science, and Bachelor's degree from IIT Kanpur advised by Surender Baswana.
Contact
Princeton: 219, Computer Science
IAS: 108, Building A
Email: kothari@cs.princeton.edu
Teaching
Fall 2016
COS 521: Advanced Algorithm Design (with Sanjeev Arora )
Tue-Thu 1:30-3pm Room: E-quad A224. First Meeting: Sep 15.
COS 597F: Proofs, Beliefs and Algorithms through the lens of Sum of Squares (with David Steurer)
Monday 1:30pm-4:20pm Friend 108 (Princeton U) First Meeting: Sep 19.
Research
I am broadly interested in theoretical computer science. Specifically, most of my recent work has been centered around understanding the power of generic algorithmic schemes based on linear and semidefinite programming relaxations, theoretical machine learning and pseudorandomness. Currently, a major focus in my research is to understand the power of the sum-of-squares method in the context of 1) algorithm design - in order to obtain fast approximation algorithms for problems in Combinatorial Optimization and Machine Learning and 2) average case complexity - in order to gather evidence of hardness and computational vs statistical complexity tradeoffs for solving random/typical instances of hard optimization problems.
Papers
Kernel Learning Via Association Schemes (with Roi Livni )
2017
The power of sum-of-squares for detecting hidden structures (with Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
2017
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) (with Boaz Barak , Zvika Brakerski and Ilan Komargodski )
2017
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture (with Boaz Barak and David Steurer)
STOC, 2017 (to appear)
Sum-of-Squares Lower Bounds for Refuting any CSP (with Ryuhei Mori , Ryan O'Donnell and David Witmer )
STOC, 2017 (to appear)
Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs (with Raghu Meka and Prasad Raghavendra )
STOC, 2017 (to appear)
Invited to SICOMP Special Issue for STOC 2017
A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique (with Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin )
FOCS 2016.
Invited to SICOMP Special Issue for FOCS 2016
[Video- IAS CS/DM Seminar] [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)
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 Stuff
A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs
(with Madan Musuvathi, Sebastian Burckhardt and Santosh Nagarakatte)
ASPLOS 2010
Kernel Learning Via Association Schemes (with Roi Livni )
2017
The power of sum-of-squares for detecting hidden structures (with Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
2017
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) (with Boaz Barak , Zvika Brakerski and Ilan Komargodski )
2017
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture (with Boaz Barak and David Steurer)
STOC, 2017 (to appear)
Sum-of-Squares Lower Bounds for Refuting any CSP (with Ryuhei Mori , Ryan O'Donnell and David Witmer )
STOC, 2017 (to appear)
Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs (with Raghu Meka and Prasad Raghavendra )
STOC, 2017 (to appear)
Invited to SICOMP Special Issue for STOC 2017
A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique (with Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin )
FOCS 2016.
Invited to SICOMP Special Issue for FOCS 2016
[Video- IAS CS/DM Seminar] [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)
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 Stuff
A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs
(with Madan Musuvathi, Sebastian Burckhardt and Santosh Nagarakatte)
ASPLOS 2010
Talks
Upcoming
STOC 2017
Sum-of-Squares Lower Bounds for Refuting any CSP (Monday, June 19)
Approximating Rectangles by Juntas and a Weakly Exponential Lower Bounds for LP Relaxations of CSPs (Tuesday, June 20)
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture (Thursday, June 22)
Past
Sum-of-Squares Meets Program Obfuscation
Stanford Crypto Reading Group [ May 26 ]
The Entanglement Frontier
Princeton Math Undergraduate Colloquium [April 28]
Sum of Squares Lower Bounds for Refuting any CSP
Member Seminar, IAS, Princeton, Fall 16
Theory Lunch, Weizmann Institute of Science - March 2017
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
[VIDEO]
Slides
Stanford Theory Seminar [May 24]
Princeton Theory Lunch [May 18]
Simons Algorithms and Geometry Meeting, Spring 2016
Columbia University Theory Seminar [Jan 27 2017]
UIUC Theory Seminar [Feb 6 2017]
QuICS Seminar, UMD [Feb 22]
CMU Theory Lunch [Mar 1]
IQC Colloquium, U. Waterloo [Mar 6]
Approximating CSPs Requires Weakly Exponential Size LPs Slides
Member Seminar Institute for Advanced Study, Fall 16
University of Chicago Theory Seminar, Fall 16
Princeton Theory Lunch, Fall 16
Capital Area Theory Seminar [Feb 17]
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Slides
Rutgers University Theory Seminar, Fall 16
Algorithms and Complexity Seminar, MIT, Summer 2016
CS/DM Seminar, Institute for Advanced Study, Princeton, Spring 2016
Workshop on Semidefinite Optimization, NUS, Singapore, Spring 2016
Sum of Squares Lower Bounds from Pairwise Independence
Slides
Cornell Theory Seminar, Spring 2016
UT Austin Theory Seminar
MSR/Harvard/MIT Reading Group
China Theory Week, Shanghai Jiao Tong University, Shanghai, China, Summer 2015
STOC 2015
Almost Optimal Pseudorandom Generators for Spherical Caps
Slides STOC 2015
Provable Submodular Minimization Using Wolfe's Algorithm
MSR Cambridge ML Reading Group, Fall 2015
Learning Coverage Functions and Private Release of Marginals
Slides
COLT 2014
Representation, Approximation and Learning of Submodular Functions Using Low-Rank Decision Trees
Slides
China Theory Week, Aarhus University, Denmark Summer 2013,
COLT 2013
Constructing Hard Functions from Learning Algorithms
Slides
CCC 2013