Pravesh Kothari

Computer Science Department Faculty - Pravesh Kothari

Adjunct Faculty


Computer Science Department

Research Interests

Jun-Ting Hsieh
Peter Manohar
Jeff Xu

Research/Teaching Statement

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.


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