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

Pravesh K. Kothari

picture
picture
Assistant Professor (Jan 2024-)
Computer Science, Applied Mathematics (PACM, Associated Faculty)
Princeton University
kothari AT cs.princeton.edu

Upcoming Talks/Events

Keynote Lecture, FSTTCS, Goa, India [Dec 25]
Yale Foundations of Data Science Colloquium [Sep 25]
Simons Symposium on New Frontiers in Combinatoric and Computer Science, Schloss Elmau, Germany[Aug 25]
Plenary lecture,ALGA Workshop [June 25]
Computer Science Commencement Address, IIT Kanpur [June 25]
Dagstuhl Workshop on Constraint Satisfaction Problems [May 25]
Lectures at Workshop on Geometry, Probability, and Algorithms [May 25]
Workshop on Graph Expansion and Applications, Princeton University[April 25]
UT Austin Theory Seminar [Mar 25]
Applied Math Colloquium, Princeton [Mar 25]
Columbia Theory Seminar [Jan 25]
Luca Trevisan Memorial Workshop at TCC, Bocconi University, Milan [Dec 24]
Luca Trevisan Memorial Workshop, Simons Institute, Berkeley [Oct 24]
IndiCS seminar on Continuous methods in discrete optimization and complexity [Oct 24]
Cornell Theory Seminar [Oct 24]
Eastern Great Lakes Workshop, Buffalo [Oct 24]
Cargèse Workshop on Combinatorial Optimization [Sep'24]
Bernoulli Center Workshop on Synergies of Combinatorics and theoretical computer science [Aug'24]
Presburger Award Talk, ICALP, Tallinn, Estonia [July 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]

Research Interests

Semidefinite Programming, Spectral Methods, Random Matrices, Extremal Combinatorics, Robust Statistics, High Dimensional Probability
My work is generously supported by an NSF CAREER Award (2021), an Alfred P. Sloan Fellowship (2022), a Google Research Scholar Award (2021), an NSF Medium Grant for collaborative research with Venkat Guruswami (2022), a 2024 seed grant from the Princeton AI Laboratory (joint with Amir Ali Ahmadi), a 2025 Princeton School of Enginering and Applied Sciences Innovation Grant (joint with Amir Ali Ahmadi), and an AI for Math Award (with Raghu Meka, UCLA) from Rennaisance Philanthropy.

Research Highlights

Complete list of my papers. Some highlights/resources:

Current Teaching

COS 330: Great Theoretical Ideas in Computer Science

Service

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, ITCS 2025, STOC 2025, FSTTCS 2025, ITCS 2026

Advising

Former Postdocs:
Alperen Ergür (Fall 2019-20, now Assistant Professor of Math and CS at UT San Antonio),
Mitali Bafna (Fall 2022-23, now Assistant Professor of CS at University of Washington)
Max Hopkins (Fall 24-25) now postdoc at School of Math, IAS

Former PhD Students:
Ainesh Bakshi (co-advised with David Woodruff, graduated 2022, Assistant Professor of CS at NYU, postdoc at MIT Math 2022-25)
Tim Hsieh (now postdoc at MIT Math),
Peter Manohar (winner of the 2023 Cylab Presidential Fellowship, co-advised with Venkat Guruswami, now postdoc at IAS School of Math),
Xinyu Wu (winner of the MSR Ada Lovelace Fellowship, co-advised with Ryan O'Donnell),
Jeff Xu (winner of the 2022 Cylab Presidential Fellowship, now postdoc at TTI Chicago)

Current PhD Students
Rohit Agarwal
Arpon Basu
Andrew Lin
Undergraduates:
Shuchen Li (now theory PhD student at Yale University)
Prashanti Anderson ( Alan J Perlis Award for student teaching, runner up to the Alan Newell award for best undergraduate SCS thesis for 2023), now PhD student at MIT EECS,
Misha Ivkov (winner of the Mark Stehlik SCS Alumni Undergraduate Impact Scholarship,now PhD student at Stanford CS),
Zachary Sussman (winner of the Alan Newell Award for best undergraduate SCS Thesis)

Some Representative Papers (for all papers, see here)

Spectral Refutations 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

Applications

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.