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
110 2006 Frame packing algorithms for automotive applications R Saket, N Navet
Journal of Embedded Computing 2 (1), 93-102, 2006
103 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 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
58 2016 On the hardness of learning intersections of two halfspaces S Khot, R Saket
Journal of Computer and System Sciences 77 (1), 129-141, 2011
50 2011 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
40 2013 Hardness of minimizing and learning DNF expressions S Khot, R Saket
2008 49th Annual IEEE Symposium on Foundations of Computer Science, 231-240, 2008
40 2008 Hardness of reconstructing multivariate polynomials over finite fields P Gopalan, S Khot, R Saket
SIAM Journal on Computing 39 (6), 2598-2621, 2010
33 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
32 2015 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
32 2006 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
25 2012 Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with S Khot, R Saket
SIAM Journal on Computing 46 (1), 235-271, 2017
24 2017 Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 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 Approximate Lasserre integrality gap for unique games S Khot, P Popat, R Saket
International Workshop on Randomization and Approximation Techniques in …, 2010
22 2010 On the Inapproximability of Vertex Cover on k -Partite k -Uniform Hypergraphs V Guruswami, R Saket
International Colloquium on Automata, Languages, and Programming, 360-371, 2010
20 2010 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
17 2014 New and improved bounds for the minimum set cover problem R Saket, M Sviridenko
International Workshop on Approximation Algorithms for Combinatorial …, 2012
16 2012 Inapproximability of Minimum Vertex Cover on V Guruswami, S Sachdeva, R Saket
SIAM Journal on Discrete Mathematics 29 (1), 36-58, 2015
14 2015 Dynamic blockchain transactional policy management V Pandit, R Saket, K Sampath, TA Siddiqui
US Patent 11,386,405, 2022
12 2022 