Subhash A. Khot, Ph.D.
Affiliations: | 2003 | Princeton University, Princeton, NJ |
Area:
Uses of randomness in complexity theory and algorithms; Efficient algorithms for finding approximate solutions to NP-hard problems (or proving that they don't exist); Cryptography.Google:
"Subhash Khot"Parents
Sign in to add mentor| Sanjeev Arora | grad student | 2003 | Princeton | |
| (New techniques for probabilistically checkable proofs and inapproximability results.) | ||||
BETA: Related publications
See more...
Publications
|
You can help our author matching system! If you notice any publications incorrectly attributed to this author, please sign in and mark matches as correct or incorrect. |
| Bhangale A, Khot S. (2019) UG-hardness to NP-hardness by losing half Electronic Colloquium On Computational Complexity. 26: 4 |
| Khot S, Saket R. (2017) Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors Siam Journal On Computing. 46: 235-271 |
| Khot SA, Vishnoi NK. (2015) The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into ℓ1 Journal of the Acm. 62: 8 |
| Khot SA, Popat P, Vishnoi NK. (2014) Almost polynomial factor hardness for closest vector problem with preprocessing Siam Journal On Computing. 43: 1184-1205 |
| Austrin P, Khot S. (2014) A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem Ieee Transactions On Information Theory. 60: 6636-6645 |
| Khot S, Moshkovitz D. (2013) NP-Hardness of approximately solving linear equations over reals Siam Journal On Computing. 42: 752-791 |
| Khot S, Naor A. (2013) Sharp kernel clustering algorithms and their associated Grothendieck inequalities Random Structures and Algorithms. 42: 269-300 |
| Khot SA, Popat P, Vishnoi NK. (2012) 2 log1-εn hardness for the closest vector problem with preprocessing Proceedings of the Annual Acm Symposium On Theory of Computing. 277-288 |
| Austrin P, Khot S, Safra M. (2011) Inapproximability of vertex cover and independent set in bounded degree graphs Theory of Computing. 7: 27-43 |
| Khot S, Saket R. (2011) On the hardness of learning intersections of two halfspaces Journal of Computer and System Sciences. 77: 129-141 |