×

zbMATH — the first resource for mathematics

Saket, Rishi

Compute Distance To:
Author ID: saket.rishi Recent zbMATH articles by "Saket, Rishi"
Published as: Saket, Rishi
Documents Indexed: 26 Publications since 2006

Publications by Year

Citations contained in zbMATH

19 Publications have been cited 55 times in 51 Documents Cited by Year
SDP integrality gaps with local \(\ell_1\)-embeddability. Zbl 1292.90228
Khot, Subhash; Saket, Rishi
9
2009
Integrality gaps for sparsest cut and minimum linear arrangement problems. Zbl 1301.05332
Devanur, Nikhil R.; Khot, Subhash A.; Saket, Rishi; Vishnoi, Nisheeth K.
8
2006
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
5
2017
On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs. Zbl 1288.68093
Guruswami, Venkatesan; Saket, Rishi
4
2010
Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors. Zbl 1359.68109
Khot, Subhash; Saket, Rishi
3
2017
Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. Zbl 1423.68193
Khot, Subhash; Saket, Rishi
3
2014
New and improved bounds for the minimum set cover problem. Zbl 1372.68306
Saket, Rishi; Sviridenko, Maxim
3
2012
Hardness of reconstructing multivariate polynomials over finite fields. Zbl 1211.68210
Gopalan, Parikshit; Khot, Subhash; Saket, Rishi
3
2010
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
Approximating CSPs using LP relaxation. Zbl 1440.68103
Khot, Subhash; Saket, Rishi
2
2015
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2012
Quasi-random PCP and hardness of 2-catalog segmentation. Zbl 1245.68095
Saket, Rishi
2
2010
On hardness of learning intersection of two halfspaces. Zbl 1231.68139
Khot, Subhash; Saket, Rishi
2
2008
Hardness of embedding metric spaces of equal size. Zbl 1171.68871
Khot, Subhash; Saket, Rishi
2
2007
On the approximability of digraph ordering. Zbl 1372.68302
Kenkre, Sreyash; Pandit, Vinayaka; Purohit, Manish; Saket, Rishi
1
2017
Inapproximability of minimum vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1331.68089
Guruswami, Venkatesan; Sachdeva, Sushant; Saket, Rishi
1
2015
The approximability of the binary paintshop problem. Zbl 1407.68194
Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath; Saket, Rishi; Schieber, Baruch
1
2013
Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1343.68100
Sachdeva, Sushant; Saket, Rishi
1
2011
On the hardness of learning intersections of two halfspaces. Zbl 1213.68496
Khot, Subhash; Saket, Rishi
1
2011
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
5
2017
Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors. Zbl 1359.68109
Khot, Subhash; Saket, Rishi
3
2017
On the approximability of digraph ordering. Zbl 1372.68302
Kenkre, Sreyash; Pandit, Vinayaka; Purohit, Manish; Saket, Rishi
1
2017
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
Approximating CSPs using LP relaxation. Zbl 1440.68103
Khot, Subhash; Saket, Rishi
2
2015
Inapproximability of minimum vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1331.68089
Guruswami, Venkatesan; Sachdeva, Sushant; Saket, Rishi
1
2015
Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. Zbl 1423.68193
Khot, Subhash; Saket, Rishi
3
2014
The approximability of the binary paintshop problem. Zbl 1407.68194
Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath; Saket, Rishi; Schieber, Baruch
1
2013
New and improved bounds for the minimum set cover problem. Zbl 1372.68306
Saket, Rishi; Sviridenko, Maxim
3
2012
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2012
Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1343.68100
Sachdeva, Sushant; Saket, Rishi
1
2011
On the hardness of learning intersections of two halfspaces. Zbl 1213.68496
Khot, Subhash; Saket, Rishi
1
2011
On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs. Zbl 1288.68093
Guruswami, Venkatesan; Saket, Rishi
4
2010
Hardness of reconstructing multivariate polynomials over finite fields. Zbl 1211.68210
Gopalan, Parikshit; Khot, Subhash; Saket, Rishi
3
2010
Quasi-random PCP and hardness of 2-catalog segmentation. Zbl 1245.68095
Saket, Rishi
2
2010
SDP integrality gaps with local \(\ell_1\)-embeddability. Zbl 1292.90228
Khot, Subhash; Saket, Rishi
9
2009
On hardness of learning intersection of two halfspaces. Zbl 1231.68139
Khot, Subhash; Saket, Rishi
2
2008
Hardness of embedding metric spaces of equal size. Zbl 1171.68871
Khot, Subhash; Saket, Rishi
2
2007
Integrality gaps for sparsest cut and minimum linear arrangement problems. Zbl 1301.05332
Devanur, Nikhil R.; Khot, Subhash A.; Saket, Rishi; Vishnoi, Nisheeth K.
8
2006
all top 5

Cited by 103 Authors

7 Saket, Rishi
6 Guruswami, Venkatesan
6 Khot, Subhash Ajit
4 Naor, Assaf
3 Raghavendra, Prasad
2 Barenboim, Leonid
2 Charikar, Moses S.
2 Elkin, Michael
2 Gavoille, Cyril
2 Håstad, Johan Torkel
2 Karpinski, Marek
2 Mossel, Elchanan
2 Naumov, Pavel G.
2 Schmied, Richard
2 Tao, Jia
2 Viehmann, Claus
1 Andoni, Alexandr
1 Arkin, Esther M.
1 Bandeira, Afonso S.
1 Banik, Aritra
1 Barak, Boaz
1 Bazzi, Abbas
1 Bhangale, Amey
1 Bhaskara, Aditya
1 Caprara, Alberto
1 Cardinal, Jean-Paul
1 Carmi, Paz
1 Citovsky, Gui
1 Çivril, Ali
1 De, Anindya K.
1 Dell, Holger
1 Diakonikolas, Ilias
1 Dinur, Irit
1 Du, Donglei
1 El Ouali, Mourad
1 Feige, Uriel
1 Fiorini, Samuel
1 Fohlin, Helena
1 Fuerst, Carlo
1 Gandikota, Venkata
1 Ghazi, Badih
1 Gillis, Nicolas
1 Gopalan, Parikshit
1 Grigorescu, Elena
1 Hajiaghayi, Mohammad Taghi
1 Harsha, Prahladh
1 Karlin, Anna R.
1 Karloff, Howard J.
1 Katz, Matthew J.
1 Kenkre, Sreyash
1 Kennedy, Christopher A.
1 Kim, Eun Jung
1 Krauthgamer, Robert
1 Lampis, Michael
1 Lee, Euiwoong
1 Letchford, Adam N.
1 Liu, Zilong
1 Mathieu, Claire
1 Meka, Raghu
1 Mitchell, Joseph S. B.
1 Mitsou, Valia
1 Mömke, Tobias
1 Neeman, Joe
1 Nguyen, C. Thach
1 Oleszkiewicz, Krzysztof
1 Pacut, Maciej
1 Palazuelos, Carlos
1 Pandit, Vinayaka
1 Pokutta, Sebastian
1 Purohit, Manish
1 Rao, Satish B.
1 Razenshteyn, Ilya P.
1 Reichman, Daniel
1 Rotter, Daniel
1 Sachdeva, Sushant
1 Salazar-González, Juan-José
1 Sandeep, Sai
1 Schmid, Stefan
1 Servedio, Rocco A.
1 Shenmaier, V. V.
1 Shenmaier, Vladimir
1 Sherstov, Alexander A.
1 Simakov, Marina
1 Singer, Amit
1 Srinivasan, Srikanth
1 Srivastav, Anand
1 Steurer, David
1 Svensson, Ola
1 Tan, Ning
1 Thiruvenkatachari, Devanathan
1 Tian, Fang
1 Trevisan, Luca
1 Varma, Girish
1 Vavasis, Stephen A.
1 Vidick, Thomas
1 Vijayaraghavan, Aravindan
1 Vishnoi, Nisheeth K.
1 Vygen, Jens
1 Wu, Yi
1 Xu, Dachuan
...and 3 more Authors

Citations by Year