Pravesh Kothari

Computer Science Department Faculty - Pravesh Kothari

Adjunct Faculty

Email praveshk@andrew.cmu.edu

Department
Computer Science Department

Research Interests
Theory

Advisees
Jun-Ting Hsieh
Jeff Xu

My current research aims at designing efficient algorithms and obtaining rigorous evidence of algorithmic thresholds for average-case computational problems arising in theoretical computer science and its intersections with allied areas such as statistics. Part of this research program is currently supported by an NSF CAREER Award (2021-2026) on The Nature of Average-Case Computation and a Sloan Fellowship (2022).


One highlight of this research program has been the development of sum-of-squares method that brings in ideas from proof complexity to give an "on-demand" design and analysis of semidefinite programming relaxations for hard optimization problems. See my recent monograph Semialgebraic Proofs and Efficient Algorithm Design with Pitassi and Fleming for an introduction and lecture notes from my Fall 2021 CMU class for details.


Publications

Journal Article

Strongly refuting all semi-random Boolean CSPs

2021 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 454-472
Abascal J, Guruswami V, Kothari PK