\( \newcommand{\pmset}{ \{\pm 1\}} \newcommand{\on}{\{\pm 1\}} \newcommand{\cM}{\mathcal{M}} \newcommand{\R}{\mathbb{R}} \)

Pravesh K. Kothari's homepage

picture

Research Instructor
Department of Computer Science, Princeton University
Institute for Advanced Study, Princeton

Brief Bio

Before moving to Princeton, 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.

Recent/Upcoming Events/Talks

ICERM Workshop on Real Algebraic Geometry and Optimization, Providence, RI [Oct'18]
ICTS Workshop on Algorithms and Optimization, Bangalore, India [Jan'18]
Simons Workshop on Hierarchies, Extended Formulations and Matrix-Analytic Techniques, Berkeley, CA [Nov 2017]
Columbia Theory Seminar [Oct 27]
Guest Lecture: Seminar on New Directions in Theoretical Machine Learning, Princeton CS [Oct 2017]
FOCS 2017 [Oct 2017]
Oberwolfach Workshop on Proof Complexity and Beyond, Oberwolfach, Germany [Aug 2017]

Contact

Email: "lastname" at cs dot princeton dot edu
Offices: Simonyi 007 (IAS, Default) and 413 (35, Olden Street, Princeton)

Research

I am broadly interested in theoretical computer science. 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 Machine Learning, Combinatorial Optimization and beyond 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.

Preprints/Upcoming

Outlier-Robust Moment Estimation Via Sum-of-Squares
With David Steurer Show Abstract

Better Agnostic Clustering Via Relaxed Tensor Norms
With Jacob Steinhardt Show Abstract

SoS Lower Bounds with Hard Constraints: Think Global, Act Local
With Ryan O'Donnell and Tselil Schramm . Show Abstract

Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
With Boaz Barak and David Steurer Show Abstract

Selected Recent Papers (for all papers, see here)

The power of sum-of-squares for detecting hidden structures
With Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
FOCS 2017 Show Abstract

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
With Boaz Barak , Zvika Brakerski and Ilan Komargodski
2017 Show Abstract

Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
With Boaz Barak and David Steurer
STOC, 2017 Show Abstract

Sum-of-Squares Lower Bounds for Refuting any CSP
With Ryuhei Mori , Ryan O'Donnell and David Witmer
STOC, 2017 Show Abstract

Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs
With Raghu Meka and Prasad Raghavendra
STOC, 2017
Invited to SICOMP Special Issue for STOC 2017 Show Abstract

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. [Video- IAS CS/DM Seminar] [Boaz's WOT post]
Invited to SICOMP Special Issue for FOCS 2016 Show Abstract

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 .) Show Abstract

Provable Submodular Minimization Using Wolfe's Algorithm
With Deeparnab Chakrabarty and Prateek Jain
NIPS 2014 (Oral Presentation) Show Abstract