Year |
Citation |
Score |
2019 |
Bhangale A, Khot S. UG-hardness to NP-hardness by losing half Electronic Colloquium On Computational Complexity. 26: 4. DOI: 10.4230/Lipics.Ccc.2019.3 |
0.301 |
|
2017 |
Khot S, Saket R. Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors Siam Journal On Computing. 46: 235-271. DOI: 10.1137/15100240X |
0.349 |
|
2015 |
Khot SA, Vishnoi NK. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into ℓ1 Journal of the Acm. 62: 8. DOI: 10.1145/2629614 |
0.39 |
|
2014 |
Khot SA, Popat P, Vishnoi NK. Almost polynomial factor hardness for closest vector problem with preprocessing Siam Journal On Computing. 43: 1184-1205. DOI: 10.1137/130919623 |
0.425 |
|
2014 |
Austrin P, Khot S. A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem Ieee Transactions On Information Theory. 60: 6636-6645. DOI: 10.1109/Tit.2014.2340869 |
0.311 |
|
2013 |
Khot S, Moshkovitz D. NP-Hardness of approximately solving linear equations over reals Siam Journal On Computing. 42: 752-791. DOI: 10.1137/110846415 |
0.319 |
|
2013 |
Khot S, Naor A. Sharp kernel clustering algorithms and their associated Grothendieck inequalities Random Structures and Algorithms. 42: 269-300. DOI: 10.1002/Rsa.20398 |
0.347 |
|
2012 |
Khot SA, Popat P, Vishnoi NK. 2 log1-εn hardness for the closest vector problem with preprocessing Proceedings of the Annual Acm Symposium On Theory of Computing. 277-288. DOI: 10.1145/2213977.2214004 |
0.334 |
|
2011 |
Austrin P, Khot S, Safra M. Inapproximability of vertex cover and independent set in bounded degree graphs Theory of Computing. 7: 27-43. DOI: 10.4086/Toc.2011.V007A003 |
0.348 |
|
2011 |
Khot S, Saket R. On the hardness of learning intersections of two halfspaces Journal of Computer and System Sciences. 77: 129-141. DOI: 10.1016/J.Jcss.2010.06.010 |
0.391 |
|
2011 |
Alekhnovich M, Khot SA, Kindler G, Vishnoi NK. Hardness of Approximating the Closest Vector Problem with Pre-Processing Computational Complexity. 20: 741-753. DOI: 10.1007/S00037-011-0031-3 |
0.369 |
|
2011 |
Chakrabarti A, Khot S. Combinatorial theorems about embedding trees on the real line Journal of Graph Theory. 67: 153-168. DOI: 10.1002/Jgt.20608 |
0.376 |
|
2010 |
Gopalan P, Khot S, Saket R. Hardness of reconstructing multivariate polynomials over finite fields Siam Journal On Computing. 39: 2598-2621. DOI: 10.1137/070705258 |
0.354 |
|
2009 |
Karloff H, Khot S, Mehta A, Rabani Y. On Earthmover Distance, Metric Labeling, and 0-Extension Siam Journal On Computing. 39: 371-387. DOI: 10.1137/070685671 |
0.445 |
|
2009 |
Feldman V, Gopalan P, Khot S, Ponnuswami AK. On Agnostic Learning of Parities, Monomials, and Halfspaces Siam Journal On Computing. 39: 606-645. DOI: 10.1137/070684914 |
0.311 |
|
2009 |
Khot S, Naor A. Approximate kernel clustering Mathematika. 55: 129-165. DOI: 10.1112/S002557930000098X |
0.411 |
|
2008 |
Khot S, Naor A. Linear equations modulo 2 and the L1 diameter of convex bodies Siam Journal On Computing. 38: 1448-1463. DOI: 10.1137/070691140 |
0.423 |
|
2008 |
Khot S, Regev O. Vertex cover might be hard to approximate to within 2 - ε Journal of Computer and System Sciences. 74: 335-349. DOI: 10.1016/J.Jcss.2007.06.019 |
0.373 |
|
2007 |
Khot S, Kindler G, Mossel E, O'Donnell R. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? Siam Journal On Computing. 37: 319-357. DOI: 10.1137/S0097539705447372 |
0.409 |
|
2007 |
Chakrabarti A, Khot S. Improved lower bounds on the randomized complexity of graph properties Random Structures and Algorithms. 30: 427-440. DOI: 10.1002/Rsa.V30:3 |
0.387 |
|
2006 |
Khot S. Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique Siam Journal On Computing. 36: 1025-1071. DOI: 10.1137/S0097539705447037 |
0.466 |
|
2006 |
Khot S. Hardness of approximating the Shortest Vector Problem in high ℓp norms Journal of Computer and System Sciences. 72: 206-219. DOI: 10.1016/J.Jcss.2005.07.002 |
0.368 |
|
2005 |
Håstad J, Khot S. Query efficient PCPs with perfect completeness Theory of Computing. 1: 119-148. DOI: 10.4086/Toc.2005.V001A007 |
0.368 |
|
2005 |
Khot S. Hardness of approximating the shortest vector problem in lattices Journal of the Acm. 52: 789-808. DOI: 10.1145/1089023.1089027 |
0.453 |
|
2005 |
Khot S. Guest column: inapproximability results via Long Code based PCPs Sigact News. 36: 25-42. DOI: 10.1145/1067309.1067318 |
0.369 |
|
2005 |
Dinur I, Guruswami V, Khot S, Regev O. A new multilayered PCP and the hardness of hypergraph vertex cover Siam Journal On Computing. 34: 1129-1146. DOI: 10.1137/S0097539704443057 |
0.424 |
|
2004 |
Jayram TS, Khot S, Kumar R, Rabani Y. Cell-probe lower bounds for the partial match problem Journal of Computer and System Sciences. 69: 435-447. DOI: 10.1016/J.Jcss.2004.04.006 |
0.403 |
|
2002 |
Chakrabarti A, Khot S, Shi Y. Evasiveness of Subgraph Containment and Related Properties Siam Journal On Computing. 31: 866-875. DOI: 10.1137/S0097539700382005 |
0.39 |
|
Show low-probability matches. |