Search the dblp DataBase

Publications of Author

1. Subhash Khot, Rishi Saket
   A 3-Query Non-Adaptive PCP with Perfect Completeness. [Citation Graph (0, 0)][DBLP]
   IEEE Conference on Computational Complexity, 2006, pp:159-169 [Conf]
   
2. Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi
   Integrality gaps for sparsest cut and minimum linear arrangement problems. [Citation Graph (0, 0)][DBLP]
   STOC, 2006, pp:537-546 [Conf]
   
3. Subhash Khot, Rishi Saket
   Hardness of Embedding Metric Spaces of Equal Size. [Citation Graph (0, 0)][DBLP]
   APPROX-RANDOM, 2007, pp:218-227 [Conf]
   
4. 
   Approximate Lasserre Integrality Gap for Unique Games. [Citation Graph (, )][DBLP]
   
   
5. 
   Hardness of Reconstructing Multivariate Polynomials over Finite Fields. [Citation Graph (, )][DBLP]
   
   
6. 
   Hardness of Minimizing and Learning DNF Expressions. [Citation Graph (, )][DBLP]
   
   
7. 
   SDP Integrality Gaps with Local ell_1-Embeddability. [Citation Graph (, )][DBLP]
   
   
8. 
   On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs. [Citation Graph (, )][DBLP]
   
   
9. 
   On hardness of learning intersection of two halfspaces. [Citation Graph (, )][DBLP]
   
   
10. 
    Hardness of Reconstructing Multivariate Polynomials over Finite Fields. [Citation Graph (, )][DBLP]