| 2008 |
|---|
| 63 | EE | Subhash Khot,
Ashok Kumar Ponnuswami:
Minimizing Wide Range Regret with Time Selection Functions.
COLT 2008: 81-86 |
| 62 | EE | Subhash Khot,
Rishi Saket:
Hardness of Minimizing and Learning DNF Expressions.
FOCS 2008: 231-240 |
| 61 | EE | Subhash Khot,
Assaf Naor:
Approximate Kernel Clustering.
FOCS 2008: 561-570 |
| 60 | EE | Sanjeev Arora,
Subhash Khot,
Alexandra Kolla,
David Steurer,
Madhur Tulsiani,
Nisheeth K. Vishnoi:
Unique games on expanding constraint graphs are easy: extended abstract.
STOC 2008: 21-28 |
| 59 | EE | Subhash Khot,
Rishi Saket:
On hardness of learning intersection of two halfspaces.
STOC 2008: 345-354 |
| 58 | EE | Subhash Khot,
Richard J. Lipton,
Evangelos Markakis,
Aranyak Mehta:
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Algorithmica 52(1): 3-18 (2008) |
| 57 | EE | Subhash Khot,
Assaf Naor:
Approximate kernel clustering
CoRR abs/0807.4626: (2008) |
| 56 | EE | Subhash Khot,
Oded Regev:
Vertex cover might be hard to approximate to within 2-epsilon.
J. Comput. Syst. Sci. 74(3): 335-349 (2008) |
| 55 | EE | Subhash Khot,
Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
SIAM J. Comput. 38(4): 1448-1463 (2008) |
| 2007 |
|---|
| 54 | EE | Subhash Khot,
Ashok Kumar Ponnuswami:
Approximation Algorithms for the Max-Min Allocation Problem.
APPROX-RANDOM 2007: 204-217 |
| 53 | EE | Subhash Khot,
Rishi Saket:
Hardness of Embedding Metric Spaces of Equal Size.
APPROX-RANDOM 2007: 218-227 |
| 52 | EE | Subhash Khot,
Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
FOCS 2007: 318-328 |
| 51 | EE | Parikshit Gopalan,
Subhash Khot,
Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
FOCS 2007: 349-359 |
| 50 | EE | Parikshit Gopalan,
Subhash Khot,
Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
Electronic Colloquium on Computational Complexity (ECCC) 14(073): (2007) |
| 49 | EE | Amit Chakrabarti,
Subhash Khot:
Improved lower bounds on the randomized complexity of graph properties.
Random Struct. Algorithms 30(3): 427-440 (2007) |
| 48 | EE | Subhash Khot,
Guy Kindler,
Elchanan Mossel,
Ryan O'Donnell:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput. 37(1): 319-357 (2007) |
| 2006 |
|---|
| 47 | EE | Subhash Khot,
Ryan O'Donnell:
SDP gaps and UGC-hardness for MAXCUTGAIN.
FOCS 2006: 217-226 |
| 46 | EE | Vitaly Feldman,
Parikshit Gopalan,
Subhash Khot,
Ashok Kumar Ponnuswami:
New Results for Learning Noisy Parities and Halfspaces.
FOCS 2006: 563-574 |
| 45 | EE | Subhash Khot,
Ashok Kumar Ponnuswami:
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.
ICALP (1) 2006: 226-237 |
| 44 | EE | Subhash Khot,
Rishi Saket:
A 3-Query Non-Adaptive PCP with Perfect Completeness.
IEEE Conference on Computational Complexity 2006: 159-169 |
| 43 | EE | Nikhil R. Devanur,
Subhash Khot,
Rishi Saket,
Nisheeth K. Vishnoi:
Integrality gaps for sparsest cut and minimum linear arrangement problems.
STOC 2006: 537-546 |
| 42 | EE | Howard J. Karloff,
Subhash Khot,
Aranyak Mehta,
Yuval Rabani:
On earthmover distance, metric labeling, and 0-extension.
STOC 2006: 547-556 |
| 41 | EE | Vitaly Feldman,
Parikshit Gopalan,
Subhash Khot,
Ashok Kumar Ponnuswami:
New Results for Learning Noisy Parities and Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC) 13(059): (2006) |
| 40 | EE | Subhash Khot:
Hardness of approximating the Shortest Vector Problem in high lp norms.
J. Comput. Syst. Sci. 72(2): 206-219 (2006) |
| 39 | EE | Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique.
SIAM J. Comput. 36(4): 1025-1071 (2006) |
| 2005 |
|---|
| 38 | EE | Subhash Khot,
Assaf Naor:
Nonembeddability theorems via Fourier analysis.
FOCS 2005: 101-112 |
| 37 | EE | Mikhail Alekhnovich,
Subhash Khot,
Guy Kindler,
Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
FOCS 2005: 216-225 |
| 36 | EE | Subhash Khot:
On the Unique Games Conjecture.
FOCS 2005: 3 |
| 35 | EE | Subhash Khot,
Nisheeth K. Vishnoi:
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.
FOCS 2005: 53-62 |
| 34 | EE | Venkatesan Guruswami,
Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses.
IEEE Conference on Computational Complexity 2005: 154-162 |
| 33 | EE | Subhash Khot,
Richard J. Lipton,
Evangelos Markakis,
Aranyak Mehta:
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
WINE 2005: 92-101 |
| 32 | EE | Howard J. Karloff,
Subhash Khot,
Aranyak Mehta,
Yuval Rabani:
On earthmover distance, metric labeling, and 0-extension
Electronic Colloquium on Computational Complexity (ECCC)(064): (2005) |
| 31 | EE | Guy Kindler,
Ryan O'Donnell,
Subhash Khot,
Elchanan Mossel:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electronic Colloquium on Computational Complexity (ECCC)(101): (2005) |
| 30 | EE | Subhash Khot:
Hardness of approximating the shortest vector problem in lattices.
J. ACM 52(5): 789-808 (2005) |
| 29 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput. 34(5): 1129-1146 (2005) |
| 28 | EE | Subhash Khot:
Guest column: inapproximability results via Long Code based PCPs.
SIGACT News 36(2): 25-42 (2005) |
| 27 | EE | Johan Håstad,
Subhash Khot:
Query Efficient PCPs with Perfect Completeness.
Theory of Computing 1(1): 119-148 (2005) |
| 2004 |
|---|
| 26 | EE | Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in Lattices.
FOCS 2004: 126-135 |
| 25 | EE | Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.
FOCS 2004: 136-145 |
| 24 | EE | Subhash Khot,
Guy Kindler,
Elchanan Mossel,
Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
FOCS 2004: 146-154 |
| 23 | EE | Jonas Holmerin,
Subhash Khot:
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.
STOC 2004: 11-20 |
| 22 | EE | T. S. Jayram,
Subhash Khot,
Ravi Kumar,
Yuval Rabani:
Cell-probe lower bounds for the partial match problem.
J. Comput. Syst. Sci. 69(3): 435-447 (2004) |
| 2003 |
|---|
| 21 | EE | Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in High Lp Norms.
FOCS 2003: 290-297 |
| 20 | EE | Amit Chakrabarti,
Subhash Khot,
Xiaodong Sun:
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.
IEEE Conference on Computational Complexity 2003: 107-117 |
| 19 | EE | Jonas Holmerin,
Subhash Khot:
A Strong Inapproximability Gap for a Generalization of Minimum Bisection.
IEEE Conference on Computational Complexity 2003: 371-378 |
| 18 | EE | Subhash Khot,
Oded Regev:
Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.
IEEE Conference on Computational Complexity 2003: 379- |
| 17 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover.
STOC 2003: 595-601 |
| 16 | EE | T. S. Jayram,
Subhash Khot,
Ravi Kumar,
Yuval Rabani:
Cell-probe lower bounds for the partial match problem.
STOC 2003: 667-672 |
| 15 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
CoRR cs.CC/0304026: (2003) |
| 14 | EE | Sanjeev Arora,
Subhash Khot:
Fitting algebraic curves to noisy data.
J. Comput. Syst. Sci. 67(2): 325-340 (2003) |
| 2002 |
|---|
| 13 | EE | Subhash Khot:
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.
FOCS 2002: 23-32 |
| 12 | EE | Subhash Khot:
On the Power of Unique 2-Prover 1-Round Games.
IEEE Conference on Computational Complexity 2002: 25 |
| 11 | EE | Sanjeev Arora,
Subhash Khot:
Fitting algebraic curves to noisy data.
STOC 2002: 162-169 |
| 10 | EE | Subhash Khot:
Hardness results for approximate hypergraph coloring.
STOC 2002: 351-359 |
| 9 | EE | Subhash Khot:
On the power of unique 2-prover 1-round games.
STOC 2002: 767-775 |
| 8 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot:
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electronic Colloquium on Computational Complexity (ECCC)(027): (2002) |
| 7 | | Subhash Khot,
Venkatesh Raman:
Parameterized complexity of finding subgraphs with hereditary properties.
Theor. Comput. Sci. 289(2): 997-1008 (2002) |
| 2001 |
|---|
| 6 | | Subhash Khot:
Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.
FOCS 2001: 600-609 |
| 5 | | Johan Håstad,
Subhash Khot:
Query Efficient PCPs with Perfect Completeness.
FOCS 2001: 610-619 |
| 4 | EE | Amit Chakrabarti,
Subhash Khot:
Improved Lower Bounds on the Randomized Complexity of Graph Properties.
ICALP 2001: 285-296 |
| 3 | EE | Amit Chakrabarti,
Subhash Khot,
Yaoyun Shi:
Evasiveness of Subgraph Containment and Related Properties.
STACS 2001: 110-120 |
| 2 | EE | Amit Chakrabarti,
Subhash Khot,
Yaoyun Shi:
Evasiveness of Subgraph Containment and Related Properties.
SIAM J. Comput. 31(3): 866-875 (2001) |
| 2000 |
|---|
| 1 | EE | Subhash Khot,
Venkatesh Raman:
Parameterized Complexity of Finding Subgraphs with Hereditary Properties.
COCOON 2000: 137-147 |
