Follow
Prasad Raghavendra
Prasad Raghavendra
Verified email at cs.berkeley.edu
Title
Cited by
Cited by
Year
Optimal algorithms and inapproximability results for every CSP?
P Raghavendra
Proceedings of the fortieth annual ACM symposium on Theory of computing, 245-254, 2008
4902008
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
A Roychoudhury, M D'Souza
373*2012
Graph expansion and the unique games conjecture
P Raghavendra, D Steurer
Proceedings of the forty-second ACM symposium on Theory of computing, 755-764, 2010
2992010
Lower bounds on the size of semidefinite programming relaxations
JR Lee, P Raghavendra, D Steurer
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
2042015
Hardness of learning halfspaces with noise
V Guruswami, P Raghavendra
SIAM Journal on Computing 39 (2), 742-765, 2009
1952009
Beating the random ordering is hard: Every ordering CSP is approximation resistant
V Guruswami, J Håstad, R Manokaran, P Raghavendra, M Charikar
SIAM Journal on Computing 40 (3), 878-914, 2011
194*2011
Rounding semidefinite programming hierarchies via global correlation
B Barak, P Raghavendra, D Steurer
2011 ieee 52nd annual symposium on foundations of computer science, 472-481, 2011
1842011
Agnostic learning of monomials by halfspaces is hard
V Feldman, V Guruswami, P Raghavendra, Y Wu
SIAM Journal on Computing 41 (6), 1558-1590, 2012
1782012
The power of sum-of-squares for detecting hidden structures
SB Hopkins, PK Kothari, A Potechin, P Raghavendra, T Schramm, ...
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
1522017
Approximate constraint satisfaction requires large LP relaxations
SO Chan, JR Lee, P Raghavendra, D Steurer
Journal of the ACM (JACM) 63 (4), 1-22, 2016
1492016
Reductions between expansion problems
P Raghavendra, D Steurer, M Tulsiani
2012 IEEE 27th Conference on Computational Complexity, 64-73, 2012
1372012
Approximating CSPs with global cardinality constraints using SDP hierarchies
P Raghavendra, N Tan
Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete …, 2012
1302012
Integrality gaps for strong SDP relaxations of unique games
P Raghavendra, D Steurer
2009 50th Annual IEEE Symposium on Foundations of Computer Science, 575-585, 2009
1062009
A birthday repetition theorem and complexity of approximating dense CSPs
P Manurangsi, P Raghavendra
arXiv preprint arXiv:1607.02986, 2016
1032016
Many sparse cuts via higher eigenvalues
A Louis, P Raghavendra, P Tetali, S Vempala
Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012
952012
SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling
R Manokaran, J Naor, P Raghavendra, R Schwartz
Proceedings of the fortieth annual ACM symposium on Theory of computing, 11-20, 2008
932008
Making the long code shorter
B Barak, P Gopalan, J Håstad, R Meka, P Raghavendra, D Steurer
SIAM Journal on Computing 44 (5), 1287-1324, 2015
922015
How to round any CSP
P Raghavendra, D Steurer
2009 50th Annual IEEE Symposium on Foundations of Computer Science, 586-594, 2009
832009
Beating the random assignment on constraint satisfaction problems of bounded degree
B Barak, A Moitra, R O'Donnell, P Raghavendra, O Regev, D Steurer, ...
arXiv preprint arXiv:1505.03424, 2015
812015
List decodable learning via sum of squares
P Raghavendra, M Yau
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
782020
The system can't perform the operation now. Try again later.
Articles 1–20