pith. sign in

Subhash Khot

Identifiers

  • name variant Subhash Khot 0.60 · backfill

Papers (17)

  1. Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems cs.LG · 2026 · author #2
  2. On Approximability of Satisfiable k-CSPs: V cs.CC · 2024 · author #2
  3. The Andoni--Krauthgamer--Razenshteyn characterization of sketchable norms fails for sketchable metrics cs.DS · 2018 · author #1
  4. Near-optimal approximation algorithm for simultaneous Max-Cut cs.CC · 2018 · author #2
  5. An Improved Dictatorship Test with Perfect Completeness cs.CC · 2017 · author #2
  6. An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness cs.DS · 2016 · author #1
  7. Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs cs.CC · 2013 · author #1
  8. A Characterization of Approximation Resistance cs.CC · 2013 · author #1
  9. A Characterization of Approximation Resistance for Even $k$-Partite CSPs cs.CC · 2013 · author #2
  10. $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing cs.CC · 2011 · author #1
  11. Grothendieck-type inequalities in combinatorial optimization cs.DS · 2011 · author #1
  12. A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem cs.CC · 2010 · author #2
  13. Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) cs.CC · 2010 · author #5
  14. Sharp kernel clustering algorithms and their associated Grothendieck inequalities cs.DS · 2009 · author #1
  15. Approximate kernel clustering cs.DS · 2008 · author #1
  16. Nonembeddability theorems via Fourier analysis math.FA · 2005 · author #1
  17. A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover cs.CC · 2003 · author #3

Mentions

  • 2606.01329 #2 · arxiv_oai · confidence 0.70 Subhash Khot
  • 1308.3247 #1 · backfill · confidence 0.70 Subhash Khot
  • 1305.5500 #1 · backfill · confidence 0.70 Subhash Khot
  • 1301.2731 #2 · backfill · confidence 0.70 Subhash Khot
  • 1109.2176 #1 · backfill · confidence 0.70 Subhash Khot
  • 1108.2464 #1 · backfill · confidence 0.70 Subhash Khot
  • 2408.15377 #2 · arxiv_oai · confidence 0.70 Subhash Khot
  • 1010.1481 #2 · backfill · confidence 0.70 Subhash Khot
  • 1002.3864 #5 · backfill · confidence 0.70 Subhash Khot
  • 0906.4816 #1 · backfill · confidence 0.70 Subhash Khot
  • 0807.4626 #1 · backfill · confidence 0.70 Subhash Khot

Frequent Coauthors