Publications

10 results for Subhash Khot

Hardness of coloring 2-colorable 12-uniform hypergraphs with 2^{(log n)}^ω(1) colors
- - Subhash Khot
  - Rishi Saket
- 2017
- SIAM Journal on Computing
Hardness of bipartite expansion
- - Subhash Khot
  - Rishi Saket
- 2016
- ESA 2016
Hardness of coloring 2-colorable 12-uniform hypergraphs with 2^(logn}ω(1) colors
- - Subhash Khot
  - Rishi Saket
- 2014
- FOCS 2014
Hardness of finding independent sets in almost q-colorable graphs
- - Subhash Khot
  - Rishi Saket
- 2012
- FOCS 2012
Optimal long code test with one free bit
- - Nikhil Bansal
  - Subhash Khot
- 2009
- FOCS 2009
Inapproximability results for combinatorial auctions with submodular utility functions
- - Subhash Khot
  - Richard J. Lipton
  - et al.
- 2007
- Algorithmica (New York)
On earthmover distance, metric labeling, and 0-extension
- - Howard Karloff
  - Subhash Khot
  - et al.
- 2006
- STOC 2006
Integrality gaps for sparsest cut and minimum linear arrangement problems
- - Nikhil R. Devanur
  - Subhash A. Khot
  - et al.
- 2006
- STOC 2006
Cell-probe lower bounds for the partial match problem
- - T.S. Jayram
  - Subhash Khot
  - et al.
- 2004
- Journal of Computer and System Sciences
Cell-probe lower bounds for the partial match problem
- - T.S. Jayram
  - Subhash Khot
  - et al.
- 2003
- STOC 2003