Travelled to:1 × Denmark
1 × France
1 × Greece
1 × Italy
1 × Japan
1 × Switzerland
2 × Canada
6 × USA
Collaborated with:R.Saket ∅ M.Tulsiani N.K.Vishnoi P.Worah S.Arora P.Popat P.Austrin D.Moshkovitz N.Bansal A.K.Ponnuswami Y.Rabani J.Holmerin A.Chakrabarti V.Guruswami N.R.Devanur H.J.Karloff A.Mehta I.Dinur O.Regev T.S.Jayram R.Kumar R.O'Donnell Y.Wu A.Kolla D.Steurer
Talks about:approxim (5) problem (5) hard (5) hypergraph (3) linear (3) cover (3) gap (3) inapproxim (2) minimum (2) distanc (2)
Person: Subhash Khot
DBLP: Khot:Subhash
Contributed to:
20152014
201420122011201120102008200620062004200320022001Wrote 20 papers:
- ICALP-v1-2015-KhotS #approximate #using
- Approximating CSPs Using LP Relaxation (SK, RS), pp. 822–833.
- ICALP-v1-2014-KhotTW #approximate #complexity
- The Complexity of Somewhat Approximation Resistant Predicates (SK, MT, PW), pp. 689–700.
- STOC-2014-KhotTW #approximate
- A characterization of strong approximation resistance (SK, MT, PW), pp. 634–643.
- STOC-2012-KhotPV #preprocessor #problem
- 2log1-ε n hardness for the closest vector problem with preprocessing (SK, PP, NKV), pp. 277–288.
- ICALP-v1-2011-AustrinK #distance #problem #reduction
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem (PA, SK), pp. 474–485.
- STOC-2011-KhotM #approximate #equation #linear #np-hard
- NP-hardness of approximately solving linear equations over reals (SK, DM), pp. 413–420.
- ICALP-v1-2010-BansalK #problem #scheduling
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems (NB, SK), pp. 250–261.
- ICALP-v1-2010-GuruswamiKOPTW
- SDP Gaps for 2-to-1 and Other Label-Cover Variants (VG, SK, RO, PP, MT, YW), pp. 617–628.
- STOC-2008-AroraKKSTV #constraints #game studies #graph
- Unique games on expanding constraint graphs are easy: extended abstract (SA, SK, AK, DS, MT, NKV), pp. 21–28.
- STOC-2008-KhotS #learning #on the
- On hardness of learning intersection of two halfspaces (SK, RS), pp. 345–354.
- ICALP-v1-2006-KhotP #clique
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion (SK, AKP), pp. 226–237.
- STOC-2006-DevanurKSV #linear #problem
- Integrality gaps for sparsest cut and minimum linear arrangement problems (NRD, SK, RS, NKV), pp. 537–546.
- STOC-2006-KarloffKMR #distance #metric #on the
- On earthmover distance, metric labeling, and 0-extension (HJK, SK, AM, YR), pp. 547–556.
- STOC-2004-HolmerinK #equation #linear #verification
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisection (JH, SK), pp. 11–20.
- STOC-2003-DinurGKR #multi
- A new multilayered PCP and the hardness of hypergraph vertex cover (ID, VG, SK, OR), pp. 595–601.
- STOC-2003-JayramKKR #bound #problem
- Cell-probe lower bounds for the partial match problem (TSJ, SK, RK, YR), pp. 667–672.
- STOC-2002-AroraK #algebra #semistructured data
- Fitting algebraic curves to noisy data (SA, SK), pp. 162–169.
- STOC-2002-Khot #approximate
- Hardness results for approximate hypergraph coloring (SK), pp. 351–359.
- STOC-2002-Khot02a #game studies #on the #power of
- On the power of unique 2-prover 1-round games (SK), pp. 767–775.
- ICALP-2001-ChakrabartiK #bound #complexity #graph #random
- Improved Lower Bounds on the Randomized Complexity of Graph Properties (AC, SK), pp. 285–296.