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 Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random 2022 • Annual ACM Symposium on Theory of Computing • 678-689 Guruswami V, Kothari PK, Manohar P Conference Playing Unique Games on Certified Small-Set Expanders 2021 • Annual ACM Symposium on Theory of Computing • 1629-1642 Bafna M, Barak B, Kothari PK, Schramm T, Steurer D 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 Conference Sparse PCA: Algorithms, Adversarial Perturbations and Certificates 2020 • Annual Symposium on Foundations of Computer Science • 553-564 D'Orsi T, Kothari PK, Novikov G, Steurer D Journal Article Tight bounds on <i>l</i><sub>1</sub> approximation and learning of self-bounding functions 2020 • Theoretical Computer Science • 808:86-98 Feldman V, Kothari P, Vondrak J
Journal Article Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random 2022 • Annual ACM Symposium on Theory of Computing • 678-689 Guruswami V, Kothari PK, Manohar P
Conference Playing Unique Games on Certified Small-Set Expanders 2021 • Annual ACM Symposium on Theory of Computing • 1629-1642 Bafna M, Barak B, Kothari PK, Schramm T, Steurer D
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
Conference Sparse PCA: Algorithms, Adversarial Perturbations and Certificates 2020 • Annual Symposium on Foundations of Computer Science • 553-564 D'Orsi T, Kothari PK, Novikov G, Steurer D
Journal Article Tight bounds on <i>l</i><sub>1</sub> approximation and learning of self-bounding functions 2020 • Theoretical Computer Science • 808:86-98 Feldman V, Kothari P, Vondrak J
