×

zbMATH — the first resource for mathematics

Raghavendra, Prasad

Compute Distance To:
Author ID: raghavendra.prasad Recent zbMATH articles by "Raghavendra, Prasad"
Published as: Raghavendra, Prasad
External Links: MGP
Documents Indexed: 59 Publications since 2007, including 1 Book

Publications by Year

Citations contained in zbMATH

43 Publications have been cited 352 times in 257 Documents Cited by Year
Optimal algorithms and inapproximability results for every CSP? Zbl 1231.68142
Raghavendra, Prasad
56
2008
Lower bounds on the size of semidefinite programming relaxations. Zbl 1321.90099
Lee, James R.; Raghavendra, Prasad; Steurer, David
44
2015
Approximate constraint satisfaction requires large LP relaxations. Zbl 1394.68170
Chan, Siu On; Lee, James R.; Raghavendra, Prasad; Steurer, David
32
2016
Graph expansion and the unique games conjecture. Zbl 1293.05373
Raghavendra, Prasad; Steurer, David
26
2010
Rounding semidefinite programming hierarchies via global correlation. Zbl 1292.90226
Barak, Boaz; Raghavendra, Prasad; Steurer, David
15
2011
Beating the random ordering is hard: every ordering CSP is approximation resistant. Zbl 1235.68075
Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses
14
2011
Approximating CSPs with global cardinality constraints using SDP hierarchies. Zbl 1422.68312
Raghavendra, Prasad; Tan, Ning
11
2012
Integrality gaps for strong SDP relaxations of unique games. Zbl 1292.90230
Raghavendra, Prasad; Steurer, David
11
2009
SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling (extended abstract). Zbl 1231.68140
Manokaran, Raisekar; Naor, Joseph (Seffi); Raghavendra, Prasad; Schwartz, Roy
11
2008
Improved approximation algorithms for the spanning star forest problem. Zbl 1171.05424
Chen, Ning; Engelberg, Roee; Nguyen, C. Thach; Raghavendra, Prasad; Rudra, Atri; Singh, Gyanit
10
2007
Coarse differentiation and multi-flows in planar graphs. Zbl 1213.05056
Lee, James R.; Raghavendra, Prasad
9
2010
How to round any CSP. Zbl 1292.90231
Raghavendra, Prasad; Steurer, David
9
2009
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. Zbl 1370.68133
Kothari, Pravesh K.; Meka, Raghu; Raghavendra, Prasad
8
2017
Many sparse cuts via higher eigenvalues. Zbl 1286.05095
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh
8
2012
On mimicking networks representing minimum terminal cuts. Zbl 1284.05295
Khan, Arindam; Raghavendra, Prasad
7
2014
Improved approximation algorithms for the spanning star forest problem. Zbl 1275.68159
Chen, Ning; Engelberg, Roee; Nguyen, C. Thach; Raghavendra, Prasad; Rudra, Atri; Singh, Gyanit
6
2013
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. Zbl 1294.68083
Diakonikolas, Ilias; Harsha, Prahladh; Klivans, Adam; Meka, Raghu; Raghavendra, Prasad; Servedio, Rocco A.; Tan, Li-Yang
6
2010
Making the long code shorter. Zbl 1330.68089
Barak, Boaz; Gopalan, Parikshit; Håstad, Johan; Meka, Raghu; Raghavendra, Prasad; Steurer, David
5
2015
Approximations for the isoperimetric and spectral profile of graphs and related parameters. Zbl 1293.05214
Raghavendra, Prasad; Steurer, David; Tetali, Prasad
5
2010
Approximating sparsest cut in graphs of bounded treewidth. Zbl 1304.68213
Chlamtac, Eden; Krauthgamer, Robert; Raghavendra, Prasad
5
2010
Hardness of learning halfspaces with noise. Zbl 1198.68157
Guruswami, Venkatesan; Raghavendra, Prasad
5
2009
Average sensitivity and noise sensitivity of polynomial threshold functions. Zbl 1311.68081
Diakonikolas, Ilias; Raghavendra, Prasad; Servedio, Rocco A.; Tan, Li-Yang
4
2014
Agnostic learning of monomials by halfspaces is hard. Zbl 1261.68063
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2012
List decoding tensor products and interleaved codes. Zbl 1235.94073
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
4
2011
Algorithmic extensions of Cheeger’s inequality to higher eigenvalues and partitions. Zbl 1321.05152
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh
4
2011
Agnostic learning of monomials by halfspaces is hard. Zbl 1292.68097
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2009
Towards computing the Grothendieck constant. Zbl 1422.68135
Raghavendra, Prasad; Steurer, David
3
2009
A birthday repetition theorem and complexity of approximating dense CSPs. Zbl 1441.68048
Manurangsi, Pasin; Raghavendra, Prasad
2
2017
Real stability testing. Zbl 1402.65041
Raghavendra, Prasad; Ryder, Nick; Srivastava, Nikhil
2
2017
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
On the integrality gap of degree-4 sum of squares for planted clique. Zbl 1410.05156
Hopkins, Samuel B.; Kothari, Pravesh; Potechin, Aaron Henry; Raghavendra, Prasad; Schramm, Tselil
2
2016
The matching problem has no small symmetric SDP. Zbl 1423.90209
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
2
2016
Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John
2
2015
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2012
Testing odd-cycle-freeness in Boolean functions. Zbl 1259.68149
Bhattacharyya, Arnab; Grigorescu, Elena; Raghavendra, Prasad; Shapira, Asaf
2
2012
Buffer management for colored packets with deadlines. Zbl 1253.68067
Azar, Yossi; Feige, Uriel; Gamzu, Iftah; Moscibroda, Thomas; Raghavendra, Prasad
2
2011
A 3-query PCP over integers. Zbl 1232.68065
Guruswami, Venkatesan; Raghavendra, Prasad
2
2007
On the bit complexity of sum-of-squares proofs. Zbl 1441.68100
Raghavendra, Prasad; Weitz, Benjamin
1
2017
The matching problem has no small symmetric SDP. Zbl 1373.90094
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
1
2017
Correlation decay and tractability of CSPs. Zbl 1388.68301
Brown-Cohen, Jonah; Raghavendra, Prasad
1
2016
List decoding tensor products and interleaved codes. Zbl 1304.94119
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
1
2009
Constraint satisfaction over a non-Boolean domain: Approximation algorithms and unique-games hardness. Zbl 1159.68665
Guruswami, Venkatesan; Raghavendra, Prasad
1
2008
On proactive perfectly secure message transmission. Zbl 1213.68101
Srinathan, Kannan; Raghavendra, Prasad; Rangan Chandrasekaran, Pandu
1
2007
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. Zbl 1370.68133
Kothari, Pravesh K.; Meka, Raghu; Raghavendra, Prasad
8
2017
A birthday repetition theorem and complexity of approximating dense CSPs. Zbl 1441.68048
Manurangsi, Pasin; Raghavendra, Prasad
2
2017
Real stability testing. Zbl 1402.65041
Raghavendra, Prasad; Ryder, Nick; Srivastava, Nikhil
2
2017
On the bit complexity of sum-of-squares proofs. Zbl 1441.68100
Raghavendra, Prasad; Weitz, Benjamin
1
2017
The matching problem has no small symmetric SDP. Zbl 1373.90094
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
1
2017
Approximate constraint satisfaction requires large LP relaxations. Zbl 1394.68170
Chan, Siu On; Lee, James R.; Raghavendra, Prasad; Steurer, David
32
2016
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
On the integrality gap of degree-4 sum of squares for planted clique. Zbl 1410.05156
Hopkins, Samuel B.; Kothari, Pravesh; Potechin, Aaron Henry; Raghavendra, Prasad; Schramm, Tselil
2
2016
The matching problem has no small symmetric SDP. Zbl 1423.90209
Braun, Gábor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
2
2016
Correlation decay and tractability of CSPs. Zbl 1388.68301
Brown-Cohen, Jonah; Raghavendra, Prasad
1
2016
Lower bounds on the size of semidefinite programming relaxations. Zbl 1321.90099
Lee, James R.; Raghavendra, Prasad; Steurer, David
44
2015
Making the long code shorter. Zbl 1330.68089
Barak, Boaz; Gopalan, Parikshit; Håstad, Johan; Meka, Raghu; Raghavendra, Prasad; Steurer, David
5
2015
Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John
2
2015
On mimicking networks representing minimum terminal cuts. Zbl 1284.05295
Khan, Arindam; Raghavendra, Prasad
7
2014
Average sensitivity and noise sensitivity of polynomial threshold functions. Zbl 1311.68081
Diakonikolas, Ilias; Raghavendra, Prasad; Servedio, Rocco A.; Tan, Li-Yang
4
2014
Improved approximation algorithms for the spanning star forest problem. Zbl 1275.68159
Chen, Ning; Engelberg, Roee; Nguyen, C. Thach; Raghavendra, Prasad; Rudra, Atri; Singh, Gyanit
6
2013
Approximating CSPs with global cardinality constraints using SDP hierarchies. Zbl 1422.68312
Raghavendra, Prasad; Tan, Ning
11
2012
Many sparse cuts via higher eigenvalues. Zbl 1286.05095
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh
8
2012
Agnostic learning of monomials by halfspaces is hard. Zbl 1261.68063
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2012
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2012
Testing odd-cycle-freeness in Boolean functions. Zbl 1259.68149
Bhattacharyya, Arnab; Grigorescu, Elena; Raghavendra, Prasad; Shapira, Asaf
2
2012
Rounding semidefinite programming hierarchies via global correlation. Zbl 1292.90226
Barak, Boaz; Raghavendra, Prasad; Steurer, David
15
2011
Beating the random ordering is hard: every ordering CSP is approximation resistant. Zbl 1235.68075
Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses
14
2011
List decoding tensor products and interleaved codes. Zbl 1235.94073
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
4
2011
Algorithmic extensions of Cheeger’s inequality to higher eigenvalues and partitions. Zbl 1321.05152
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh
4
2011
Buffer management for colored packets with deadlines. Zbl 1253.68067
Azar, Yossi; Feige, Uriel; Gamzu, Iftah; Moscibroda, Thomas; Raghavendra, Prasad
2
2011
Graph expansion and the unique games conjecture. Zbl 1293.05373
Raghavendra, Prasad; Steurer, David
26
2010
Coarse differentiation and multi-flows in planar graphs. Zbl 1213.05056
Lee, James R.; Raghavendra, Prasad
9
2010
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. Zbl 1294.68083
Diakonikolas, Ilias; Harsha, Prahladh; Klivans, Adam; Meka, Raghu; Raghavendra, Prasad; Servedio, Rocco A.; Tan, Li-Yang
6
2010
Approximations for the isoperimetric and spectral profile of graphs and related parameters. Zbl 1293.05214
Raghavendra, Prasad; Steurer, David; Tetali, Prasad
5
2010
Approximating sparsest cut in graphs of bounded treewidth. Zbl 1304.68213
Chlamtac, Eden; Krauthgamer, Robert; Raghavendra, Prasad
5
2010
Integrality gaps for strong SDP relaxations of unique games. Zbl 1292.90230
Raghavendra, Prasad; Steurer, David
11
2009
How to round any CSP. Zbl 1292.90231
Raghavendra, Prasad; Steurer, David
9
2009
Hardness of learning halfspaces with noise. Zbl 1198.68157
Guruswami, Venkatesan; Raghavendra, Prasad
5
2009
Agnostic learning of monomials by halfspaces is hard. Zbl 1292.68097
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2009
Towards computing the Grothendieck constant. Zbl 1422.68135
Raghavendra, Prasad; Steurer, David
3
2009
List decoding tensor products and interleaved codes. Zbl 1304.94119
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
1
2009
Optimal algorithms and inapproximability results for every CSP? Zbl 1231.68142
Raghavendra, Prasad
56
2008
SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling (extended abstract). Zbl 1231.68140
Manokaran, Raisekar; Naor, Joseph (Seffi); Raghavendra, Prasad; Schwartz, Roy
11
2008
Constraint satisfaction over a non-Boolean domain: Approximation algorithms and unique-games hardness. Zbl 1159.68665
Guruswami, Venkatesan; Raghavendra, Prasad
1
2008
Improved approximation algorithms for the spanning star forest problem. Zbl 1171.05424
Chen, Ning; Engelberg, Roee; Nguyen, C. Thach; Raghavendra, Prasad; Rudra, Atri; Singh, Gyanit
10
2007
A 3-query PCP over integers. Zbl 1232.68065
Guruswami, Venkatesan; Raghavendra, Prasad
2
2007
On proactive perfectly secure message transmission. Zbl 1213.68101
Srinathan, Kannan; Raghavendra, Prasad; Rangan Chandrasekaran, Pandu
1
2007
all top 5

Cited by 468 Authors

10 Mastrolilli, Monaldo
10 Pokutta, Sebastian
8 Braun, Gábor
8 Kurpisz, Adam
7 Guruswami, Venkatesan
7 Mossel, Elchanan
6 Göös, Mika
6 Khot, Subhash Ajit
6 Leppänen, Samuli
5 Chandrasekaran, Karthekeyan
5 Raghavendra, Prasad
5 Saket, Rishi
5 Thapper, Johan
5 Xu, Dachuan
5 Živný, Stanislav
4 Fiorini, Samuel
4 Gouveia, Joao
4 Harrow, Aram Wettroth
4 Krokhin, Andrei A.
4 Pitassi, Toniann
4 Tiwary, Hans Raj
4 Trevisan, Luca
4 Wu, Chenchen
3 Bandeira, Afonso S.
3 Bérczi, Kristóf
3 Bhangale, Amey
3 Dalmau, Víctor
3 de Wolf, Ronald Michiel
3 De, Anindya K.
3 Du, Donglei
3 Goranci, Gramoz
3 Jonsson, Peter A.
3 Kane, Daniel M.
3 Király, Tamás
3 Kolla, Alexandra
3 Kolmogorov, Vladimir
3 Kortsarz, Guy
3 Kutiel, Gilad
3 Lee, Euiwoong
3 Lee, James R.
3 Lee, Troy
3 Liang, Hongyu
3 Liao, Chung-Shou
3 Makarychev, Yury S.
3 Mathieu, Claire
3 Mömke, Tobias
3 Naor, Assaf
3 Ostrovskii, Mikhail Iosifovich
3 Peng, Pan
3 Robinson, Richard Z.
3 Roy, Aurko
3 Thomas, Rekha R.
3 van Iersel, Leo
3 Watson, Thomas C.
3 Zhang, Louxin
2 Arora, Sanjeev
2 Austrin, Per
2 Averkov, Gennadiy
2 Barak, Boaz
2 Bonsma, Paul S.
2 Brandão, Fernando G. S. L.
2 Broersma, Hajo J.
2 Buchbinder, Niv
2 Chan, T.-H. Hubert
2 Chen, Hubie
2 Dey, Papri
2 Dilworth, Stephen J.
2 Faenza, Yuri
2 Faliszewski, Piotr
2 Färnqvist, Tommy
2 Fawzi, Hamza
2 Feldman, Vitaly
2 Fernau, Henning
2 Fox, Jacob
2 Gandhi, Rajiv B.
2 Georgiou, Konstantinos
2 Gutin, Gregory Z.
2 Håstad, Johan Torkel
2 He, Jing
2 Hopkins, Samuel B.
2 Jain, Rahul
2 Janssen, Teun
2 Karpinski, Marek
2 Karpov, Nikolai
2 Kelk, Steven
2 Khoshkhah, Kaveh
2 Khosravian Ghadikolaei, Mehdi
2 Kim, Eun Jung
2 Kozik, Marcin
2 Krauthgamer, Robert
2 Kuivinen, Fredrik
2 Kutzarova, Denka N.
2 Laurent, Monique
2 Louis, Anand
2 Lovász, László Miklós
2 Madan, Vivek
2 Makarychev, Konstantin S.
2 Manurangsi, Pasin
2 Meka, Raghu
2 Moitra, Ankur
...and 368 more Authors
all top 5

Cited in 74 Serials

33 SIAM Journal on Computing
18 Mathematical Programming. Series A. Series B
14 Theoretical Computer Science
8 Algorithmica
8 SIAM Journal on Discrete Mathematics
8 Computational Complexity
7 Discrete Applied Mathematics
6 Journal of Computer and System Sciences
6 Journal of Combinatorial Optimization
5 SIAM Journal on Optimization
4 Mathematics of Operations Research
4 Journal of the ACM
4 Theory of Computing
3 Communications in Mathematical Physics
3 Information Processing Letters
3 Israel Journal of Mathematics
3 Journal of Functional Analysis
3 Algorithms
3 SIAM Journal on Applied Algebra and Geometry
2 Artificial Intelligence
2 Advances in Mathematics
2 Inventiones Mathematicae
2 Journal of Combinatorial Theory. Series A
2 Probability Theory and Related Fields
2 Discrete & Computational Geometry
2 Machine Learning
2 Random Structures & Algorithms
2 Bulletin of the American Mathematical Society. New Series
2 Theory of Computing Systems
2 Foundations of Computational Mathematics
2 Discrete Optimization
1 Communications on Pure and Applied Mathematics
1 Journal of Mathematical Physics
1 Linear and Multilinear Algebra
1 Problems of Information Transmission
1 Zhurnal Vychislitel’noĭ Matematiki i Matematicheskoĭ Fiziki
1 Arkiv för Matematik
1 The Annals of Probability
1 The Annals of Statistics
1 Canadian Journal of Mathematics
1 Mathematika
1 Numerische Mathematik
1 Proceedings of the American Mathematical Society
1 European Journal of Combinatorics
1 Operations Research Letters
1 Combinatorica
1 Social Choice and Welfare
1 Journal of Symbolic Computation
1 Information and Computation
1 Computational Geometry
1 International Journal of Foundations of Computer Science
1 Geometric and Functional Analysis. GAFA
1 Pattern Recognition
1 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI
1 Finite Fields and their Applications
1 Chicago Journal of Theoretical Computer Science
1 Journal of Graph Algorithms and Applications
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 Annals of Mathematics. Second Series
1 Journal of the European Mathematical Society (JEMS)
1 RAIRO. Operations Research
1 Portugaliae Mathematica. Nova Série
1 Journal of Machine Learning Research (JMLR)
1 Quantum Information Processing
1 Journal of Discrete Algorithms
1 Journal of Industrial and Management Optimization
1 Mathematics in Computer Science
1 Electronic Journal of Statistics
1 Japanese Journal of Mathematics. 3rd Series
1 Journal of Control Science and Engineering
1 Science China. Mathematics
1 Numerical Algebra, Control and Optimization
1 ACM Transactions on Computation Theory
1 Research in the Mathematical Sciences

Citations by Year