Hardness of bipartite expansion
- Subhash Khot
- Rishi Saket
- 2016
- ESA 2016
Publications
Date
Featured collections
Popular topics
10 results for Subhash Khot
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
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.
- 2003
- STOC 2003
Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors
- Subhash Khot
- Rishi Saket
- 2017
- SIAM Journal on Computing
Inapproximability results for combinatorial auctions with submodular utility functions
- Subhash Khot
- Richard J. Lipton
- et al.
- 2007
- Algorithmica (New York)
Cell-probe lower bounds for the partial match problem
- T.S. Jayram
- Subhash Khot
- et al.
- 2004
- Journal of Computer and System Sciences