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

Pravesh K. Kothari's homepage


Assistant Professor
Theory Group
Computer Science Department, CMU
Gates 7105
praveshk AT cs.cmu.edu

Recent/Upcoming Events/Talks

International Conference on Continuous Optimization, Berlin [Aug 2019]
SIAM Conference in Applied Algebraic Geometry, Bern [Jul 2019]
BIRS Workshop on Algebraic Techniques in Computational Complexity, Banff [July 2019]
ITCS 2019, San Diego [Jan 2019]
UCLA Theory Seminar [Jan 2019]
University of Chicago Theory Seminar [Dec 2018]
Oberwolfach Workshop on Complexity Theory, Oberwolfach, Germany [Nov 2018]
ICERM Workshop on Real Algebraic Geometry and Optimization, Providence, RI [Oct'18]
Workshop on Analytic Techniques in Theoretical Computer Science, Oaxaca, Mexico [Aug 12-17]
TTI-Chicago Summer Workshop on High-Dimensional Robust Statistics [Aug 2018]
NYU Theory Seminar [May 2018]
IAS Computer Science and Discrete Mathematics Seminar, Princeton [Feb 2018]
ITCS 2018, Cambridge, MA [Jan 2018]
ICTS Workshop on Algorithms and Optimization, Bangalore, India [Jan'18]


Semialgebraic Proofs and Algorithm Design
with Toni Pitassi and Noah Fleming


PC Member APPROX/RANDOM 2018, SODA 2019, STOC 2020, ITCS 2020

Current Teaching

15-455: Undergraduate Complexity Theory
Class Material on Diderot (currently accessible only via CMU ID)
with Ryan O'Donnell
Tue-Thu 10:30-11:50am, Gates 4307
Office Hours: Wed 10:30am-12pm (or by appointment)


Postdoc: Alperen Ergür


I am broadly interested in theoretical computer science. My recent research has focused on investigating meta-algorithms such as the Sum of Squares method and Extended Formulations. Specifically, I have worked on
1) obtaining fast algorithms for problems arising in unsupervised machine learning, combinatorial optimization, quantum information and cryptography and, on the flip side,
2) obtaining general lower-bound techniques to gather evidence for tight computational vs statistical complexity trade-offs for some basic problems arising in average-case complexity.

Selected Recent Papers (for all papers, see here)

List-Decodable Linear Regression
With Sushrut Karmalkar and Adam Klivans
Preprint, 2019.

Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
With Boaz Barak and David Steurer
A generally accessible article on the recent proof of the 2-to-2 games conjecture that partly relies on this work.
Show Abstract

Efficient Algorithms for Outlier-Robust Regression
With Adam Klivans and Raghu Meka
COLT 2018 Show Abstract

An Analysis of t-SNE Algorithm for Data Visualization
With Sanjeev Arora and Wei Hu
COLT 2018 Show Abstract

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

STOC 2018 (conference version to be merged with the paper below)

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

STOC 2018 (conference version to be merged with the paper above)

Sum-of-Squares Meets Nash: Lower Bounds for finding any equilibrium
With Ruta Mehta Show Abstract

STOC 2018

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

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

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