Optimal algorithms and inapproximability results for every CSP? P Raghavendra Proceedings of the fortieth annual ACM symposium on Theory of computing, 245-254, 2008 | 487 | 2008 |
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface A Roychoudhury, M D'Souza | 368* | 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 | 298 | 2010 |
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 | 203 | 2015 |
Hardness of learning halfspaces with noise V Guruswami, P Raghavendra SIAM Journal on Computing 39 (2), 742-765, 2009 | 193 | 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 | 191* | 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 | 180 | 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 | 178 | 2012 |
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 | 149 | 2016 |
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 | 147 | 2017 |
Reductions between expansion problems P Raghavendra, D Steurer, M Tulsiani 2012 IEEE 27th Conference on Computational Complexity, 64-73, 2012 | 136 | 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 | 127 | 2012 |
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 | 106 | 2009 |
A birthday repetition theorem and complexity of approximating dense CSPs P Manurangsi, P Raghavendra arXiv preprint arXiv:1607.02986, 2016 | 102 | 2016 |
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 | 94 | 2012 |
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 | 93 | 2008 |
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 | 91 | 2015 |
How to round any CSP P Raghavendra, D Steurer 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 586-594, 2009 | 83 | 2009 |
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 | 81 | 2015 |
List decodable learning via sum of squares P Raghavendra, M Yau Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 77 | 2020 |