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

## Monograph

Semialgebraic Proofs and Algorithm Designwith Toni Pitassi and Noah Fleming

## Service

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)

## Advising

**Postdoc:**Alperen Ergür

## Research

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