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

## Postdoc Position

We are currently looking for a postdoctoral associate in the theory group at CMU co-hosted by Aayush Jain and me with an intended but flexible start date of Sep 2022. The position continues till Aug 2023 with a possibility of renewal for a second year. The topics of interest include complexity of statistical inference, semidefinite programming and applications to cryptography. Please apply by writing to Aayush Jain and me with your CV, Research Statement and three letters of references before Jan 31 2022 (soft deadline).## 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

EPFL Workshop on *Learning: Optimization and Stochastics* [Jun'22]

Dagstuhl Worshop on *The Constraint Satisfaction Problem: Complexity and Approximability* [May'22]

ARC Lecture Series, Georgia Tech [Feb'22]

IAS CS/DM Seminar [Feb'22]

FOCS Workshop on Proof Complexity [Feb'22]

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 on Polynomial Optimization [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]

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