The SCEAS System
| |||||||

## Search the dblp DataBase
Subhash Khot:
[Publications]
[Author Rank by year]
[Co-authors]
[Prefers]
[Cites]
[Cited by]
## Publications of Author- 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] - 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] - 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] - 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] - 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] - 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] - Subhash Khot, Venkatesh Raman
**Parameterized Complexity of Finding Subgraphs with Hereditary Properties.**[Citation Graph (0, 0)][DBLP] COCOON, 2000, pp:137-147 [Conf] - 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] - Johan Håstad, Subhash Khot
**Query Efficient PCPs with Perfect Completeness.**[Citation Graph (0, 0)][DBLP] FOCS, 2001, pp:610-619 [Conf] - Subhash Khot
**Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.**[Citation Graph (0, 0)][DBLP] FOCS, 2001, pp:600-609 [Conf] - Subhash Khot
**Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.**[Citation Graph (0, 0)][DBLP] FOCS, 2002, pp:23-32 [Conf] - Subhash Khot
**Hardness of Approximating the Shortest Vector Problem in High Lp Norms.**[Citation Graph (0, 0)][DBLP] FOCS, 2003, pp:290-297 [Conf] - Subhash Khot
**Hardness of Approximating the Shortest Vector Problem in Lattices.**[Citation Graph (0, 0)][DBLP] FOCS, 2004, pp:126-135 [Conf] - 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] - Subhash Khot
**On the Unique Games Conjecture.**[Citation Graph (0, 0)][DBLP] FOCS, 2005, pp:3- [Conf] - 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] - Subhash Khot, Assaf Naor
**Nonembeddability theorems via Fourier analysis.**[Citation Graph (0, 0)][DBLP] FOCS, 2005, pp:101-112 [Conf] - Subhash Khot, Nisheeth K. Vishnoi
**The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l**[Citation Graph (0, 0)][DBLP]_{1}. FOCS, 2005, pp:53-62 [Conf] - Subhash Khot, Ryan O'Donnell
**SDP gaps and UGC-hardness for MAXCUTGAIN.**[Citation Graph (0, 0)][DBLP] FOCS, 2006, pp:217-226 [Conf] - 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] - 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] - 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] - Amit Chakrabarti, Subhash Khot, Yaoyun Shi
**Evasiveness of Subgraph Containment and Related Properties.**[Citation Graph (0, 0)][DBLP] STACS, 2001, pp:110-120 [Conf] - Sanjeev Arora, Subhash Khot
**Fitting algebraic curves to noisy data.**[Citation Graph (0, 0)][DBLP] STOC, 2002, pp:162-169 [Conf] - 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] - 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] - 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] - 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] - 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] - Subhash Khot
**Hardness results for approximate hypergraph coloring.**[Citation Graph (0, 0)][DBLP] STOC, 2002, pp:351-359 [Conf] - Subhash Khot
**On the power of unique 2-prover 1-round games.**[Citation Graph (0, 0)][DBLP] STOC, 2002, pp:767-775 [Conf] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - Subhash Khot
**Hardness of approximating the Shortest Vector Problem in high**[Citation Graph (0, 0)][DBLP]*l*norms._{p} J. Comput. Syst. Sci., 2006, v:72, n:2, pp:206-219 [Journal] - 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] - 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] - 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] - 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] - 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] - 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] - Subhash Khot, Rishi Saket
**Hardness of Embedding Metric Spaces of Equal Size.**[Citation Graph (0, 0)][DBLP] APPROX-RANDOM, 2007, pp:218-227 [Conf] **Approximate Lasserre Integrality Gap for Unique Games.**[Citation Graph (, )][DBLP]**Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.**[Citation Graph (, )][DBLP]**On the Unique Games Conjecture (Invited Survey).**[Citation Graph (, )][DBLP]**Minimizing Wide Range Regret with Time Selection Functions.**[Citation Graph (, )][DBLP]**Approximate Kernel Clustering.**[Citation Graph (, )][DBLP]**Hardness of Reconstructing Multivariate Polynomials over Finite Fields.**[Citation Graph (, )][DBLP]**Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.**[Citation Graph (, )][DBLP]**Hardness of Minimizing and Learning DNF Expressions.**[Citation Graph (, )][DBLP]**Optimal Long Code Test with One Free Bit.**[Citation Graph (, )][DBLP]**SDP Integrality Gaps with Local ell_1-Embeddability.**[Citation Graph (, )][DBLP]**Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.**[Citation Graph (, )][DBLP]**SDP Gaps for 2-to-1 and Other Label-Cover Variants.**[Citation Graph (, )][DBLP]**Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities.**[Citation Graph (, )][DBLP]**On hardness of learning intersection of two halfspaces.**[Citation Graph (, )][DBLP]**Unique games on expanding constraint graphs are easy: extended abstract.**[Citation Graph (, )][DBLP]**Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.**[Citation Graph (, )][DBLP]**Approximate kernel clustering**[Citation Graph (, )][DBLP]**Sharp kernel clustering algorithms and their associated Grothendieck inequalities**[Citation Graph (, )][DBLP]**Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)**[Citation Graph (, )][DBLP]**Hardness of Reconstructing Multivariate Polynomials over Finite Fields.**[Citation Graph (, )][DBLP]**New Results for Learning Noisy Parities and Halfspaces.**[Citation Graph (, )][DBLP]
Search in 0.003secs, Finished in 0.005secs | |||||||

| |||||||

| |||||||

System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002 for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002 |