Optimal algorithms and inapproximability results for every CSP? P Raghavendra Proceedings of the fortieth annual ACM symposium on Theory of computing, 245-254, 2008 | 502 | 2008 |
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 | 303 | 2010 |
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 | 204 | 2015 |
Hardness of learning halfspaces with noise V Guruswami, P Raghavendra SIAM Journal on Computing 39 (2), 742-765, 2009 | 204 | 2009 |
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 | 192 | 2011 |
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 | 179 | 2012 |
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 | 160 | 2017 |
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 | 150 | 2016 |
Reductions between expansion problems P Raghavendra, D Steurer, M Tulsiani 2012 IEEE 27th Conference on Computational Complexity, 64-73, 2012 | 137 | 2012 |
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 | 137 | 2012 |
A birthday repetition theorem and complexity of approximating dense CSPs P Manurangsi, P Raghavendra arXiv preprint arXiv:1607.02986, 2016 | 115 | 2016 |
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 | 105 | 2009 |
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 | 99 | 2012 |
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 | 96 | 2015 |
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 | 95 | 2008 |
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 | 89 | 2015 |
How to round any CSP P Raghavendra, D Steurer 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 586-594, 2009 | 86 | 2009 |
List decodable learning via sum of squares P Raghavendra, M Yau Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 84 | 2020 |