

Prasad Raghavendra
Assistant Professor
Research Areas
Teaching Schedule
(Spring 2014)
Selected Publications
 A. Louis, P. Raghavendra, P. Tetali, and S. Vempala, "Many sparse cuts via higher eigenvalues," in STOC, 2012, pp. 11311140.
 V. Guruswami, P. Raghavendra, R. Saket, and Y. Wu, "Bypassing UGC from some optimal geometric inapproximability results," in SODA, 2012, pp. 699717.
 P. Raghavendra and N. Tan, "Approximating CSPs with global cardinality constraints using SDP hierarchies," in SODA, 2012, pp. 373387.
 B. Barak, P. Raghavendra, and D. Steurer, "Rounding Semidefinite Programming Hierarchies via Global Correlation," in FOCS, 2011, pp. 472481.
 V. Guruswami, J. H{\aa}stad, R. Manokaran, P. Raghavendra, and M. Charikar, "Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant," SIAM J. Comput., vol. 40, no. 3, pp. 878914, 2011.
 P. Gopalan, V. Guruswami, and P. Raghavendra, "List Decoding Tensor Products and Interleaved Codes," SIAM J. Comput., vol. 40, no. 5, pp. 14321462, 2011.
 P. Raghavendra and D. Steurer, "Graph expansion and the unique games conjecture," in STOC, 2010, pp. 755764.
 J. R. Lee and P. Raghavendra, "Coarse Differentiation and Multiflows in Planar Graphs," citeKey, Discrete {\&} Computational Geometry, vol. 43, no. 2, pp. 346362, 2010.
 P. Raghavendra and D. Steurer, "Towards computing the Grothendieck constant," in SODA, 2009, pp. 525534.
 P. Raghavendra and D. Steurer, "How to Round Any CSP," in FOCS, 2009, pp. 586594.
 P. Raghavendra and D. Steurer, "Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES," in FOCS, 2009, pp. 575585.
 V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu, "Agnostic Learning of Monomials by Halfspaces Is Hard," in FOCS, 2009, pp. 385394.
 V. Guruswami and P. Raghavendra, "Hardness of Solving Sparse Overdetermined Linear Systems: A 3Query PCP over Integers," TOCT, vol. 1, no. 2, 2009.
 V. Guruswami and P. Raghavendra, "Hardness of Learning Halfspaces with Noise," SIAM J. Comput., vol. 39, no. 2, pp. 742765, 2009.
 P. Raghavendra, "Optimal algorithms and inapproximability results for every CSP?," in STOC, 2008, pp. 245254.
 R. Manokaran, J. Naor, P. Raghavendra, and R. Schwartz, "Sdp gaps and ugc hardness for multiway cut, 0extension,and metric labeling," in STOC, 2008, pp. 1120.
 P. Raghavendra, "A Note on Yekhanin's Locally Decodable Codes," Electronic Colloquium on Computational Complexity (ECCC), vol. 14, no. 016, 2007.



