Research output per year
Research output per year
Search results
-
2005
Hardness of Max 3SAT with no mixed clauses
Guruswami, V. & Khot, S., 2005, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 154-162 9 p.Research output: Contribution to journal › Conference article › peer-review
-
2004
A new PCP outer verifier with applications to homogeneous linear equations and Max-Bisection
Holmerin, J. & Khot, S., 2004, In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 11-20 10 p.Research output: Contribution to journal › Conference article › peer-review
-
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
Khot, S., Kindler, G., O'Donnell, R. & Mossel, E., 2004, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 146-154 9 p.Research output: Contribution to journal › Conference article › peer-review
-
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique
Khot, S., 2004, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 136-145 10 p.Research output: Contribution to journal › Conference article › peer-review
-
2003
Vertex cover might be hard to approximate to within 2 - ε
Khot, S. & Regev, O., 2003, In: Proceedings of the Annual IEEE Conference on Computational Complexity. p. 379-386 8 p.Research output: Contribution to journal › Conference article › peer-review
-
2002
Hardness results for approximate hypergraph coloring
Khot, S., 2002, In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 351-359 9 p.Research output: Contribution to journal › Conference article › peer-review
-
Parameterized complexity of finding subgraphs with hereditary properties
Khot, S. & Raman, V., Oct 30 2002, In: Theoretical Computer Science. 289, 2, p. 997-1008 12 p.Research output: Contribution to journal › Conference article › peer-review