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 and this recent talk on our resolution of the problem of robust learning of arbitrary Gaussian mixtures.
My research is generously supported by an NSF Career Award (2021-2026) and an Award from the Google Research Scholar Program.
Recent/Upcoming Events/Talks
TCS Plus Seminar [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 2022Advising
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.
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. LONG TALK.
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). 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)