| Integrality gaps for sparsest cut and minimum linear arrangement problems NR Devanur, SA Khot, R Saket, NK Vishnoi Proceedings of the thirty-eighth annual ACM symposium on Theory of computing …, 2006 | 106 | 2006 |
| Frame packing algorithms for automotive applications R Saket, N Navet Journal of Embedded Computing 2 (1), 93-102, 2006 | 102 | 2006 |
| SDP Integrality Gaps with Local ell_1-Embeddability S Khot, R Saket 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 565-574, 2009 | 70 | 2009 |
| On the hardness of learning intersections of two halfspaces S Khot, R Saket Journal of Computer and System Sciences 77 (1), 129-141, 2011 | 47 | 2011 |
| Hardness of minimizing and learning DNF expressions S Khot, R Saket 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 231-240, 2008 | 37 | 2008 |
| Bypassing UGC from some optimal geometric inapproximability results V Guruswami, P Raghavendra, R Saket, Y Wu Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete …, 2012 | 36 | 2012 |
| Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover S Sachdeva, R Saket 2013 IEEE Conference on Computational Complexity, 219-229, 2013 | 35 | 2013 |
| A 3-query non-adaptive PCP with perfect completeness S Khot, R Saket 21st Annual IEEE Conference on Computational Complexity (CCC'06), 11 pp.-169, 2006 | 33 | 2006 |
| Hardness of reconstructing multivariate polynomials over finite fields P Gopalan, S Khot, R Saket SIAM Journal on Computing 39 (6), 2598-2621, 2010 | 31 | 2010 |
| Tight hardness of the non-commutative Grothendieck problem J Briët, O Regev, R Saket 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 1108-1122, 2015 | 27 | 2015 |
| Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with Colors S Khot, R Saket SIAM Journal on Computing 46 (1), 235-271, 2017 | 24 | 2017 |
| Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with Colors S Khot, R Saket SIAM Journal on Computing 46 (1), 235-271, 2017 | 24 | 2017 |
| Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs S Khot, R Saket Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete …, 2014 | 23 | 2014 |
| Hardness of finding independent sets in almost q-colorable graphs S Khot, R Saket 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 380-389, 2012 | 22 | 2012 |
| Approximate Lasserre integrality gap for unique games S Khot, P Popat, R Saket Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2010 | 22 | 2010 |
| On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs V Guruswami, R Saket Automata, Languages and Programming: 37th International Colloquium, ICALP …, 2010 | 19 | 2010 |
| Bypassing UGC from some optimal geometric inapproximability results V Guruswami, P Raghavendra, R Saket, Y Wu ACM Transactions on Algorithms (TALG) 12 (1), 6:1-6:25, 2016 | 17 | 2016 |
| Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs R Saket 2014 IEEE 29th Conference on Computational Complexity (CCC), 78-89, 2014 | 16 | 2014 |
| New and improved bounds for the minimum set cover problem R Saket, M Sviridenko Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2012 | 16 | 2012 |
| Inapproximability of Minimum Vertex Cover on -Uniform -Partite Hypergraphs V Guruswami, S Sachdeva, R Saket SIAM Journal on Discrete Mathematics 29 (1), 36-58, 2015 | 12 | 2015 |
