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
Conference Sum of Squares Lower Bounds for Refuting any CSP 2017 • Annual ACM Symposium on Theory of Computing • 132-145 Kothari PK, Mori R, O'Donnell R, Witmer D
