The SCEAS System
Navigation Menu
Introduction
Collection Based
Clustering
Ranking
Paper Based
Journals
Conferences
DB Status
Statistics
Search

Search the dblp DataBase

Title:
Author:
Subhash Khot: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Amit Chakrabarti, Subhash Khot, Xiaodong Sun
    Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2003, pp:107-117 [Conf]
  2. Venkatesan Guruswami, Subhash Khot
    Hardness of Max 3SAT with No Mixed Clauses. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2005, pp:154-162 [Conf]
  3. Jonas Holmerin, Subhash Khot
    A Strong Inapproximability Gap for a Generalization of Minimum Bisection. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2003, pp:371-378 [Conf]
  4. Subhash Khot
    On the Power of Unique 2-Prover 1-Round Games. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2002, pp:25- [Conf]
  5. Subhash Khot, Oded Regev
    Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2003, pp:379-0 [Conf]
  6. 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]
  7. Subhash Khot, Venkatesh Raman
    Parameterized Complexity of Finding Subgraphs with Hereditary Properties. [Citation Graph (0, 0)][DBLP]
    COCOON, 2000, pp:137-147 [Conf]
  8. Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi
    Hardness of Approximating the Closest Vector Problem with Pre-Processing. [Citation Graph (0, 0)][DBLP]
    FOCS, 2005, pp:216-225 [Conf]
  9. Johan Håstad, Subhash Khot
    Query Efficient PCPs with Perfect Completeness. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:610-619 [Conf]
  10. Subhash Khot
    Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:600-609 [Conf]
  11. Subhash Khot
    Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. [Citation Graph (0, 0)][DBLP]
    FOCS, 2002, pp:23-32 [Conf]
  12. Subhash Khot
    Hardness of Approximating the Shortest Vector Problem in High Lp Norms. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:290-297 [Conf]
  13. Subhash Khot
    Hardness of Approximating the Shortest Vector Problem in Lattices. [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:126-135 [Conf]
  14. Subhash Khot
    Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:136-145 [Conf]
  15. Subhash Khot
    On the Unique Games Conjecture. [Citation Graph (0, 0)][DBLP]
    FOCS, 2005, pp:3- [Conf]
  16. Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
    Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:146-154 [Conf]
  17. Subhash Khot, Assaf Naor
    Nonembeddability theorems via Fourier analysis. [Citation Graph (0, 0)][DBLP]
    FOCS, 2005, pp:101-112 [Conf]
  18. Subhash Khot, Nisheeth K. Vishnoi
    The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1. [Citation Graph (0, 0)][DBLP]
    FOCS, 2005, pp:53-62 [Conf]
  19. Subhash Khot, Ryan O'Donnell
    SDP gaps and UGC-hardness for MAXCUTGAIN. [Citation Graph (0, 0)][DBLP]
    FOCS, 2006, pp:217-226 [Conf]
  20. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami
    New Results for Learning Noisy Parities and Halfspaces. [Citation Graph (0, 0)][DBLP]
    FOCS, 2006, pp:563-574 [Conf]
  21. Amit Chakrabarti, Subhash Khot
    Improved Lower Bounds on the Randomized Complexity of Graph Properties. [Citation Graph (0, 0)][DBLP]
    ICALP, 2001, pp:285-296 [Conf]
  22. Subhash Khot, Ashok Kumar Ponnuswami
    Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. [Citation Graph (0, 0)][DBLP]
    ICALP (1), 2006, pp:226-237 [Conf]
  23. Amit Chakrabarti, Subhash Khot, Yaoyun Shi
    Evasiveness of Subgraph Containment and Related Properties. [Citation Graph (0, 0)][DBLP]
    STACS, 2001, pp:110-120 [Conf]
  24. Sanjeev Arora, Subhash Khot
    Fitting algebraic curves to noisy data. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:162-169 [Conf]
  25. 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]
  26. Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
    A new multilayered PCP and the hardness of hypergraph vertex cover. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:595-601 [Conf]
  27. Jonas Holmerin, Subhash Khot
    A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. [Citation Graph (0, 0)][DBLP]
    STOC, 2004, pp:11-20 [Conf]
  28. T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
    Cell-probe lower bounds for the partial match problem. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:667-672 [Conf]
  29. Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
    On earthmover distance, metric labeling, and 0-extension. [Citation Graph (0, 0)][DBLP]
    STOC, 2006, pp:547-556 [Conf]
  30. Subhash Khot
    Hardness results for approximate hypergraph coloring. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:351-359 [Conf]
  31. Subhash Khot
    On the power of unique 2-prover 1-round games. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:767-775 [Conf]
  32. Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
    Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. [Citation Graph (0, 0)][DBLP]
    WINE, 2005, pp:92-101 [Conf]
  33. Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
    A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover [Citation Graph (0, 0)][DBLP]
    CoRR, 2003, v:0, n:, pp:- [Journal]
  34. Irit Dinur, Venkatesan Guruswami, Subhash Khot
    Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:027, pp:- [Journal]
  35. Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
    On earthmover distance, metric labeling, and 0-extension [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:064, pp:- [Journal]
  36. Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel
    Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:101, pp:- [Journal]
  37. Subhash Khot
    Hardness of approximating the shortest vector problem in lattices. [Citation Graph (0, 0)][DBLP]
    J. ACM, 2005, v:52, n:5, pp:789-808 [Journal]
  38. Sanjeev Arora, Subhash Khot
    Fitting algebraic curves to noisy data. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2003, v:67, n:2, pp:325-340 [Journal]
  39. T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
    Cell-probe lower bounds for the partial match problem. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2004, v:69, n:3, pp:435-447 [Journal]
  40. Subhash Khot
    Hardness of approximating the Shortest Vector Problem in high lp norms. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2006, v:72, n:2, pp:206-219 [Journal]
  41. Amit Chakrabarti, Subhash Khot, Yaoyun Shi
    Evasiveness of Subgraph Containment and Related Properties. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2001, v:31, n:3, pp:866-875 [Journal]
  42. Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
    A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2005, v:34, n:5, pp:1129-1146 [Journal]
  43. Subhash Khot
    Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2006, v:36, n:4, pp:1025-1071 [Journal]
  44. Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
    Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2007, v:37, n:1, pp:319-357 [Journal]
  45. Subhash Khot, Venkatesh Raman
    Parameterized complexity of finding subgraphs with hereditary properties. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2002, v:289, n:2, pp:997-1008 [Journal]
  46. Subhash Khot, Ashok Kumar Ponnuswami
    Approximation Algorithms for the Max-Min Allocation Problem. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2007, pp:204-217 [Conf]
  47. Subhash Khot, Rishi Saket
    Hardness of Embedding Metric Spaces of Equal Size. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2007, pp:218-227 [Conf]

  48. Approximate Lasserre Integrality Gap for Unique Games. [Citation Graph (, )][DBLP]


  49. Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. [Citation Graph (, )][DBLP]


  50. On the Unique Games Conjecture (Invited Survey). [Citation Graph (, )][DBLP]


  51. Minimizing Wide Range Regret with Time Selection Functions. [Citation Graph (, )][DBLP]


  52. Approximate Kernel Clustering. [Citation Graph (, )][DBLP]


  53. Hardness of Reconstructing Multivariate Polynomials over Finite Fields. [Citation Graph (, )][DBLP]


  54. Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. [Citation Graph (, )][DBLP]


  55. Hardness of Minimizing and Learning DNF Expressions. [Citation Graph (, )][DBLP]


  56. Optimal Long Code Test with One Free Bit. [Citation Graph (, )][DBLP]


  57. SDP Integrality Gaps with Local ell_1-Embeddability. [Citation Graph (, )][DBLP]


  58. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. [Citation Graph (, )][DBLP]


  59. SDP Gaps for 2-to-1 and Other Label-Cover Variants. [Citation Graph (, )][DBLP]


  60. Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. [Citation Graph (, )][DBLP]


  61. On hardness of learning intersection of two halfspaces. [Citation Graph (, )][DBLP]


  62. Unique games on expanding constraint graphs are easy: extended abstract. [Citation Graph (, )][DBLP]


  63. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. [Citation Graph (, )][DBLP]


  64. Approximate kernel clustering [Citation Graph (, )][DBLP]


  65. Sharp kernel clustering algorithms and their associated Grothendieck inequalities [Citation Graph (, )][DBLP]


  66. Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) [Citation Graph (, )][DBLP]


  67. Hardness of Reconstructing Multivariate Polynomials over Finite Fields. [Citation Graph (, )][DBLP]


  68. New Results for Learning Noisy Parities and Halfspaces. [Citation Graph (, )][DBLP]


Search in 0.005secs, Finished in 0.008secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
Introduction Collection Based Clustering Ranking Paper Based Journals Conferences DB Status Statistics Search
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002