** Assistant Professor **

Theory Group

Computer Science Department, CMU

Gates 7105

praveshk AT cs.cmu.edu

## Monograph

Semialgebraic Proofs and Efficient Algorithm Designwith Noah Fleming and Toni Pitassi.

## Research

I am broadly interested in theoretical computer science. My recent research focuses on understanding algorithmic thresholds for average-case problems. See this **recent broadly accessible talk** for an overview of my research on developing the sum-of-squares method for problems in high-dimensional robust statistics. My research is generously supported by an **NSF Career Award (2021-2026)**.

## Recent/Upcoming Events/Talks

POEMA Workshop [Feb 21]

Simons Workshop on High Dimensional Learning and Testing [Dec 20]

Online CSP Seminar [Nov 20]

Simons Workshop on Computational Phase Transitions [Sep 20]

TAMU High Dimensional Probability Seminar [Aug 20]

ICERM Workshop on Symmetry, Randomness, and Computations in Real Algebraic Geometry[Aug 20]

Polynomials as an Algorithmic Paradigm, PolyAlg Seminar [June 20]

Workshop on Extension Complexity and Lifting Theorems, FSTTCS [Dec 2019]

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]

## Service

PC Member**APPROX/RANDOM 2018**,

**SODA 2019**,

**STOC 2020**,

**ITCS 2020**

## Advising

**Postdoc:**Alperen Ergür (Now Assistant Professor of Math and CS at UT San Antonio)

**Students:**Jackson Abascal (co-advised with Venkat Guruswami), Ainesh Bakshi (co-advised with David Woodruff), Tim Hsieh , Xinyu Wu (co-advised with Ryan O'Donnell), Jeff Xu

## Current Teaching

**15-859GG: Proofs vs Algorithms: The Sum-of-Squares Method ** (Diderot)

Tuesdays, 4-6:50 pm. First meeting **Sep 1**

## Selected Recent Papers (for all papers, see __here__)

**Robustly Learning a Mixture of $k$ Arbitrary Gaussians **

With Ainesh Bakshi , Ilias Diakonikolas, He Jia, Daniel Kane, Santosh Vempala

**Preprint**, 2020.

** List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time **

With Ainesh Bakshi

**SODA**, 2021 (to appear).

**Strongly refuting all semi-random Boolean CSPs**

With Jackson Abascal and Venkat Guruswami .

**SODA**, 2021 (to appear).

** Sparse PCA: algorithms, adversarial perturbations and certificates **

With Tommaso D'Orsi, Gleb Novikov, and David Steurer .

** FOCS ** 2020.

** Outlier-Robust Clustering of Non-Spherical Mixtures**

With Ainesh Bakshi

**FOCS**, 2020.

Conference version to be merged with * this * paper.

Recent

**50 min talk.**

** List-Decodable Linear Regression **

With Sushrut Karmalkar and Adam Klivans

**NeuIPS Spotlight**, 2019.

Recent **50 min talk.**

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

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

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

Recent **2 hour board talk**.

** Better Agnostic Clustering Via Relaxed Tensor Norms **

With Jacob Steinhardt
** STOC 2018 ** (conference version to be merged with the paper above)

Recent **board talk with a simpler, complete proof!.**

** Sum-of-Squares Meets Nash: Lower Bounds for finding any equilibrium **

With Ruta Mehta

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

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

** Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture**

With Boaz Barak and David Steurer

**STOC, 2017 **

Recent **50 min talk** and a shorter ** talk ** with a different perspective.

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

Recent

**50 min talk .**

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

**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 .)

**Provable Submodular Minimization Using Wolfe's Algorithm**

With Deeparnab Chakrabarty
and Prateek Jain

**NIPS 2014 (Oral Presentation) **