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

Pravesh K. Kothari

Assistant Professor (Jan 2024-)
Computer Science Department, Princeton
kothari AT cs.princeton.edu

In Spring'24, I am also affiliated with the School of Math at the IAS.

Brief Bio: I got my PhD in CS from UT Austin in Summer 2016 with a dissertation on Strong Lower Bounds on Generic Convex Relaxations. I was a postdoctoral research instructor at the IAS and Princeton CS from 2016-19 and an Assistant Professor at CSD at CMU from 2019-2023.

Upcoming Talks/Events

Cargèse Workshop on Combinatorial Optimization [Sep'24]
Bernoulli Center Workshop on Synergies of Combinatorics and theoretical computer science [Aug'24]
Workshop on Algorithms for Learning and Economics [June'24]
Plenary Session, Oberwolfach Complexity Meeting [June'24]
Milan Theory Workshop [May'24]
Oberwolfach Meeting on Proof Complexity and Beyond [March'24]
School of Math Colloquium at the Institute for Advanced Study [March 24]
EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization [Feb'24]
Banff Workshop on Computational Complexity of Statistical Inference [Feb 24]
Rutgers Theory Seminar[Feb 24]
MIT Statistics and Stochastics Seminar [Feb 24]
MIT-Harvard Reading Group [Feb 24]
Harvard Theory Seminar [Feb 24]
CSDM Seminar at the Institute for Advanced Study [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]

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, STOC 2025


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

Spectral Refutations via Kikuchi Matrices and Applications

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.