**Assistant Professor**

Theory Group

Computer Science Department, CMU

Gates 7105

praveshk AT cs.cmu.edu

## Monograph

Semialgebraic Proofs and Efficient Algorithm Design

with Noah Fleming and Toni Pitassi.

## Research

I am broadly interested in theoretical computer science. My work clusters around the meta-question:

*What structure in inputs makes efficient computation possible?
Can we formulate a picture of efficient computation and demarcate its boundaries based on the presence and absence of such structures?*

One playground for such investigations is average-case complexity -- the study of the complexity of

*random*instances of computational problems. So that forms a large part of my work -- both in finding algorithms based on new structures and in proving that there are no better algorithms (often under additional conjectures/restricted models). But frequently, it also turns out that studying average-case computation reveals structures that one can then find analogs of and thus obtain algorithms for much more general

*semi-random*instances.

As an example, see this

**recent broadly accessible talk**for an overview of my work that uses the sum-of-squares method to develop a theory of

*high dimensional robust statistics*-- the science of statistical estimation from data that deviates in an unknown way from the chosen model. A prominent example of this research is our recent solution

**(recent talk)**to the problem of robustly learning a mixture of Gaussians.

My research is generously supported by an

**NSF Career Award (2021-2026)**on

*The Nature of Average-Case Computation*and an Award from the

**Google Research Scholar Program**for

*Efficient Algorithms for Robust Machine Learning*.

## Recent/Upcoming Events/Talks

Simons Workshop on Rigorous Evidence for Information-Computation Trade-offs [Sep 21]

TCS Plus Seminar: Double Feature with Ankur Moitra on Robust Learning of Mixture of $k$ Arbitrary Gaussians [June 21]

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]

## Service

PC Member ** APPROX/RANDOM 2018**,
** SODA 2019**, ** STOC 2020**, ** ITCS 2020 **, ** NeurIPS Area Chair 2020,2021**, **CCC 2022**

## Advising

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

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

## Mentoring Talks

I recently gave two mentoring talks as part of the new workshops organized by Learning Theory Alliance.

Slides from talk on **Interacting with your Research Community. **

Slides from talk on ** Thoughts on PhD Admissions**.

## Current Teaching

**15-854B: Advanced Approximation Algorithms**** ** (with Anupam Gupta)

MWF, 10:10-11:30 am. First meeting **Aug 30**

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

**Algorithmic Thresholds for Refuting Random Polynomial Systems**

With Tim Hsieh.

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

**Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no Harder than Random**

With Venkat Guruswami and Peter Manohar

**Preprint**, 2021. __LONG TALK__.

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

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

**Preprint**, 2020. __LONG TALK__.

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

With Ainesh Bakshi

**SODA**, 2021.

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

With Jackson Abascal and Venkat Guruswami .

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

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

Conference version to be merged with * this * paper.

** List-Decodable Linear Regression **

With Sushrut Karmalkar and Adam Klivans

**NeuIPS Spotlight**, 2019. __LONG 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) ** 2 hour BOARD TALK**.

** Better Agnostic Clustering Via Relaxed Tensor Norms **

With Jacob Steinhardt
** STOC 2018 ** __BOARD TALK with a simpler, complete proof!__.

(conference version to be merged with the paper above)

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