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 HypergraphsV 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 |