\( \newcommand{\pmset}{ \{\pm 1\}} \newcommand{\on}{\{\pm 1\}} \newcommand{\cM}{\mathcal{M}} \newcommand{\R}{\mathbb{R}} \)

Pravesh K. Kothari

Assistant Professor (Sep 2019-)
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
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 average-case 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:

Current Teaching

15-251: Great Ideas in Theoretical Computer Science
with Anil Ada


Workshop Co-Chair, 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


Alperen Erg├╝r (Fall 2019-20, Now Assistant Professor of Math and CS at UT San Antonio),
Mitali Bafna (Fall 2022-23, now postdoc at MIT Math)
PhD Students:
Ainesh Bakshi (co-advised with David Woodruff, graduated 2022, now postdoc at MIT Math)
Tim Hsieh,
Peter Manohar (winner of the 2023 Cylab Presidential Fellowship, co-advised with Venkat Guruswami),
Noah Singer (co-advised with Aayush Jain),
Xinyu Wu (winner of the MSR Ada Lovelace Fellowship, co-advised with Ryan O'Donnell),
Jeff Xu (winner of the 2022 Cylab Presidential Fellowship)
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

Algorithms and Thresholds for Semirandom and Smoothed Models

Algorithmic Robust Statistics and Related Topics

Algorithms and Complexity of Unique Games and Related Problems

Average-Case Algorithmic Thresholds


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.