papers
Publications (15)
cs.DS2011
Grothendieck-type inequalities in combinatorial optimization
Subhash Khot, Assaf Naor
cs.DS2018
The Andoni--Krauthgamer--Razenshteyn characterization of sketchable norms fails for sketchable metrics
Subhash Khot, Assaf Naor
cs.CC2010
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Per Austrin, Subhash Khot
cs.DS2009
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Subhash Khot, Assaf Naor
cs.DS2016
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness
Subhash Khot, Igor Shinkar
math.FA2005
Nonembeddability theorems via Fourier analysis
Subhash Khot, Assaf Naor
cs.CC2010
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
cs.DS2008
Approximate kernel clustering
Subhash Khot, Assaf Naor
cs.CC2018
Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, Swastik Kopparty +2
cs.CC2013
A Characterization of Approximation Resistance for Even $k$-Partite CSPs
Per Austrin, Subhash Khot
cs.CC2013
A Characterization of Approximation Resistance
Subhash Khot, Madhur Tulsiani, Pratik Worah
cs.CC2003
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Irit Dinur, Venkatesan Guruswami, Subhash Khot +1
cs.CC2013
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
Subhash Khot, Rishi Saket
cs.CC2017
An Improved Dictatorship Test with Perfect Completeness
Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari
cs.CC2011
$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi