BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
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 DBLP: Khot:Subhash

Contributed to:

ICALP (1) 20152015
ICALP (1) 20142014
STOC 20142014
STOC 20122012
ICALP (1) 20112011
STOC 20112011
ICALP (1) 20102010
STOC 20082008
ICALP (1) 20062006
STOC 20062006
STOC 20042004
STOC 20032003
STOC 20022002
ICALP 20012001

Wrote 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.
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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.