Computer Science Department, CMU
Gates 7105, praveshk AT cs.cmu.edu
In Spring'24, I will be a part of the theory group at Princeton CS and the School of Math at the IAS.
Upcoming Talks/Events
Oberwolfach Complexity Meeting [June'24]
Oberwolfach Meeting on Proof Complexity and Beyond [March'24]
EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization [Feb'24]
Simons Symposium on Math of Computing According to Lattices [Aug'23]
Santa Fe Workshop on Connecting Physics, Geometry, and Algebraic Hardness [July'23]
SIAM Conference on Optimization [May'23]
Tel Aviv University Theory Fest, Plenary Session [Dec 22]
Workshop on Algorithms Under Uncertainty, Chennai [Dec 22]
Simons Institute Reunion Workshop on CCSI [Dec 22]
Princeton Center for Theoretical Science Workshop on Positivity [Nov 22]
CRM Workshop on Tensors in Algebraic Geometry [Nov'22]
Professional Mentoring Panel at FOCS 2022 [Nov'22]
UT Theory Seminar [Oct' 22]
ACO Seminar UC Irvine [Oct'22]
Berkeley Theory Lunch [Oct'22]
Stanford Theory Lunch [Oct'22]
Santa Fe Working Group on Foundations of Machine Learning [Jul'22]
Fields Workshop on Differential Privacy [Jul'22]
EPFL Workshop on Learning: Optimization and Stochastics [Jun'22]
Dagstuhl Worshop on The Constraint Satisfaction Problem: Complexity and Approximability [May'22]
MIT Theory of Computation Colloquium [April 26, '22]
Harvard Theory Seminar [April 20, '22]
Research Interests
Algorithms and computational thresholds for averagecase computational problems, random matrices, extremal combinatorics
My work is generously supported by an NSF CAREER Award (2021), an Alfred P. Sloan Fellowship (2022), a Google Research Scholar Award (2021), and an NSF Medium Grant for collaborative research with Venkat Guruswami (2022).
Research Highlights
Complete list of my papers. Some highlights/resources:

The SumofSquares Method and Algorithm Design via Connections to Proof Complexity
 Monograph on Semialgebraic Proofs and Efficient Algorithm Design.
 Fall'21 CMU Lecture notes and videos.

SumofSquares Framework for Efficient Robust Statistics
 Resolving the robust learnability of mixtures of highdimensional Gaussians (in the sequence [1], [2], and [3]) (see 2012 CACM Tech Perspective and Simons Research Vignette for history and context).
 Toolkit for basic estimation: regression, moment estimation, and sparse recovery.
 Efficient estimation in the presence of majority outliers (in the sequence [1], [2], and [3]).
 Overview talk with open questions.

The Kikuchi Matrix Method and Applications
 A new class of spectral methods for extremal combinatorics. Applications so far: refuting and solving smoothed SAT (CSPs), settling Feige's conjecture on extremal girth of hypergraphs, and improved lower bounds on locally decodable codes, and an exponential lower bound on threequery linear locally correctable codes.
 Some recent talks.

Efficient Algorithms approaching the conjectured threshold for Semirandom and Smoothed Optimization
 Refuting/solving Smoothed SAT and other CSPs(in the sequence [1], [2], [3]).
 Finding planted cliques in FeigeKilian Semirandom Model (see this book chapter and this paper for history and context on the question).
 Breaking security of certain proposed cryptographic Pseudorandom Generators.
 Some recent talks.

Pseudocalibration, the Lowdegree Polynomial Method and Sharp Computational Thresholds in AverageCase
 Lower bounds for SoS SDPs via planted vs null distinguishing problems with applications to random CSPs, planted clique, Tensor/Sparse PCA, with new connections to spectral methods and the low degree polynomial heuristic for computational phase transitions in statistical estimation
 Exponential lower bounds for linear relaxations for constraint satisfaction
 Some talks.
Current Teaching
15251: Great Ideas in Theoretical Computer Science
with Anil Ada
Service
Workshop CoChair, FOCS 2023 and 2024
PC Member APPROX/RANDOM 2018, SODA 2019, STOC 2020, ITCS 2020 , NeurIPS Area Chair 2020,2021, CCC 2022, RANDOM 2022, FSTTCS 2022, FOCS 2023
Advising
Postdocs:
Alperen Ergür (Fall 201920, Now Assistant Professor of Math and CS at UT San Antonio),
Mitali Bafna (Fall 202223, now postdoc at MIT Math)
PhD Students:
Ainesh Bakshi (coadvised with David Woodruff, graduated 2022, now postdoc at MIT Math)
Tim Hsieh,
Peter Manohar (winner of the 2023 Cylab Presidential Fellowship, coadvised with Venkat Guruswami),
Noah Singer (coadvised with Aayush Jain),
Xinyu Wu (winner of the MSR Ada Lovelace Fellowship, coadvised with Ryan O'Donnell),
Jeff Xu (winner of the 2022 Cylab Presidential Fellowship)
Undergraduates:
Prashanti Anderson (Phd student at MIT EECS, Alan J Perlis Award for student teaching, runner up to the Alan Newell award for best undergraduate SCS thesis for 2023),
Misha Ivkov (PhD student at Stanford, winner of the Mark Stehlik SCS Alumni Undergraduate Impact Scholarship),
Zachary Sussman (winner of the Alan Newell Award for best undergraduate SCS Thesis)
Some Representative Papers (for all papers, see here)
Algorithms for Learning Mixtures of Gaussians
 Robustly Learning a Mixture of $k$ Arbitrary Gaussians
With Ainesh Bakshi , Ilias Diakonikolas, He Jia, Daniel Kane, Santosh Vempala
STOC, 2022. LONG TALK.  OutlierRobust Clustering of NonSpherical Mixtures
With Ainesh Bakshi
FOCS, 2020. LONG TALK.
Conference version to be merged with this paper.  Better Agnostic Clustering Via Relaxed Tensor Norms
With Jacob Steinhardt
STOC 2018 BOARD TALK with a simpler, complete proof!.
Conference version merged with this paper.
Spectral Refutations via Kikuchi Matrices and Applications
 An Exponential Lower Bound on Linear ThreeQuery Locally Correctable Codes
With Peter Manohar
Manuscript, 2023
 A NearCubic Lower Bound for 3Query Locally Decodable Codes from Semirandom CSP Refutation
With Omar Alrabiah, Venkat Guruswami and Peter Manohar
STOC, 2023 (to appear).
Invited to SICOMP Special Issue for STOC'23
LONG TALK.  A simple and sharper proof of the hypergraph Moore bound
With Tim Hsieh and Sidhanth Mohanty
SODA, 2023.
LONG TALK.  Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no Harder than Random
With Venkat Guruswami and Peter Manohar
STOC, 2022. LONG TALK.
Invited to the SICOMP Special Issue for STOC 2022, CACM Research Highlights 2023
Algorithms and Thresholds for Semirandom and Smoothed Models
 Efficient Algorithms for Semirandom Planted CSPs at the
Refutation Threshold
With Venkat Guruswami , Tim Hsieh, and Peter Manohar
FOCS, 2023 (to appear).  Algorithms approaching the threshold for semirandom planted clique
With Rares Buhai and David Steurer
STOC, 2023 (to appear).
LONG TALK.  A simple and sharper proof of the hypergraph Moore bound
With Tim Hsieh and Sidhanth Mohanty
SODA, 2023.
LONG TALK. 
Strongly refuting all semirandom Boolean CSPs
With Jackson Abascal and Venkat Guruswami .
SODA, 2021. LONG TALK. 
SumofSquares Lower Bounds for Refuting any CSP
With Ryuhei Mori , Ryan O'Donnell and David Witmer
STOC, 2017.
Algorithmic Robust Statistics and Related Topics
 Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
With He Jia and Santosh Vempala
FOCS, 2023 (to appear).  Privately Estimating a Gaussian: Efficient, Robust and Optimal
With Daniel Alabi, Pranay Tankala, Prayaag Venkat and Fred Zhang
STOC, 2023 (to appear).  A MomentMatching Approach to Testable Learning and a New Characterization of Rademacher Complexity
With Aravind Gallakota and Adam Klivans
STOC, 2023 (to appear).
Invited to SICOMP Special Issue for STOC'23  ListDecodable Covariance Estimation
With Misha Ivkov
STOC, 2022.
 ListDecodable Subspace Recovery: Dimension Independent Error in Polynomial Time
With Ainesh Bakshi
SODA, 2021.
 ListDecodable Linear Regression
With Sushrut Karmalkar and Adam Klivans
NeuIPS Spotlight, 2019. LONG TALK. 
Sparse PCA: algorithms, adversarial perturbations and certificates
With Tommaso D'Orsi, Gleb Novikov, and David Steurer .
FOCS 2020. 
Efficient Algorithms for OutlierRobust Regression
With Adam Klivans and Raghu Meka
COLT 2018
Prasad Raghavendra's Exposition of our algorithm in a Simons Institute Bootcamp  OutlierRobust Moment Estimation Via SumofSquares
With David Steurer
STOC 2018 2 hour BOARD TALK.
Conference version merged with this paper.
Algorithms and Complexity of Unique Games and Related Problems
 Playing Unique Games on Certified SmallSet Expanders
With Mitali Bafna , Boaz Barak , Tselil Schramm and David Steurer.
STOC, 2021.
 Quantum Entanglement, SumofSquares and the LogRank Conjecture
With Boaz Barak and David Steurer
STOC, 2017
Recent 50 min talk and a shorter talk with a different perspective.  SmallSet Expansion in Shortcode Graph and the 2to1 Conjecture
With Boaz Barak and David Steurer
A generally accessible article on the recent proof of the 2to2 games conjecture that partly relies on this work.
AverageCase Algorithmic Thresholds
 Algorithmic Thresholds for Refuting Random Polynomial Systems
With Tim Hsieh.
SODA, 2022.  A StressFree SumofSquares Lower Bound for Coloring
With Peter Manohar.
CCC, 2021.
 The power of sumofsquares for detecting hidden structures
With Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
FOCS 2017
Invited to the Highlights of Algorithms (HALG) 2018 
A Nearly Tight SumofSquares 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 merged with this paper. 
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.
Applications
 SumofSquares Meets Nash: Lower Bounds for finding any equilibrium
With Ruta Mehta
STOC 2018 
Limits on LowDegree Pseudorandom Generators (Or: SumofSquares Meets Program Obfuscation)
With Boaz Barak , Zvika Brakerski and Ilan Komargodski
EUROCRYPT 2018
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.