Spremljaj
Prasad Raghavendra
Prasad Raghavendra
Preverjeni e-poštni naslov na cs.berkeley.edu
Naslov
Navedeno
Navedeno
Leto
Optimal algorithms and inapproximability results for every CSP?
P Raghavendra
Proceedings of the fortieth annual ACM symposium on Theory of computing, 245-254, 2008
5022008
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
3032010
Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics): Preface
M Abe, K Aoki, G Ateniese, R Avanzi, Z Beerliová, O Billet, A Biryukov, ...
Lecture Notes in Computer Science (including subseries Lecture Notes in …, 2006
266*2006
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
2042009
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
200*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
1922011
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
1792012
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
1602017
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
1502016
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
1372012
A birthday repetition theorem and complexity of approximating dense CSPs
P Manurangsi, P Raghavendra
arXiv preprint arXiv:1607.02986, 2016
1152016
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
1052009
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
992012
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
962015
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
952008
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
892015
How to round any CSP
P Raghavendra, D Steurer
2009 50th Annual IEEE Symposium on Foundations of Computer Science, 586-594, 2009
862009
List decodable learning via sum of squares
P Raghavendra, M Yau
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
842020
Sistem trenutno ne more izvesti postopka. Poskusite znova pozneje.
Članki 1–20