Prasad Raghavendra
Associate ProfessorInfo Links
Research Areas
Theory (THY)Research Centers
Simons Institute for the Theory of Computing (SITC)Teaching Schedule
Spring 2021
CS 270. Combinatorial Algorithms and Data Structures, MoWe 5:00PM - 6:29PM, Requested General AssignmentEducation
2009, PhD, Computer Science and Engineering, University of Washington, Seattle2007, M.S., Computer Science and Engineering, University of Washington, Seattle
2005, B.S., Computer Science, Indian Institute of Technology , Madras, India
Selected Publications
A. Louis, P. Raghavendra, P. Tetali, and S. Vempala, "Many sparse cuts via higher eigenvalues," in STOC, 2012, pp. 1131-1140.V. Guruswami, P. Raghavendra, R. Saket, and Y. Wu, "Bypassing UGC from some optimal geometric inapproximability results," in SODA, 2012, pp. 699-717.
P. Raghavendra and N. Tan, "Approximating CSPs with global cardinality constraints using SDP hierarchies," in SODA, 2012, pp. 373-387.
B. Barak, P. Raghavendra, and D. Steurer, "Rounding Semidefinite Programming Hierarchies via Global Correlation," in FOCS, 2011, pp. 472-481.
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 Journal of Computing, vol. 40, no. 3, pp. 878-914, 2011.
P. Gopalan, V. Guruswami, and P. Raghavendra, "List Decoding Tensor Products and Interleaved Codes," SIAM Journal of Computing, vol. 40, no. 5, pp. 1432-1462, 2011.
P. Raghavendra and D. Steurer, "Graph expansion and the unique games conjecture," in STOC, 2010, pp. 755-764.
J. R. Lee and P. Raghavendra, "Coarse Differentiation and Multi-flows in Planar Graphs," citeKey, Discrete {\&} Computational Geometry, vol. 43, no. 2, pp. 346-362, 2010.
P. Raghavendra and D. Steurer, "Towards computing the Grothendieck constant," in SODA, 2009, pp. 525-534.
P. Raghavendra and D. Steurer, "How to Round Any CSP," in FOCS, 2009, pp. 586-594.
P. Raghavendra and D. Steurer, "Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES," in FOCS, 2009, pp. 575-585.
V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu, "Agnostic Learning of Monomials by Halfspaces Is Hard," in FOCS, 2009, pp. 385-394.
V. Guruswami and P. Raghavendra, "Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers," TOCT, vol. 1, no. 2, 2009.
V. Guruswami and P. Raghavendra, "Hardness of Learning Halfspaces with Noise," SIAM Journal on Computing, vol. 39, no. 2, pp. 742-765, 2009.
P. Raghavendra, "Optimal algorithms and inapproximability results for every CSP?," in STOC, 2008, pp. 245-254.
R. Manokaran, J. Naor, P. Raghavendra, and R. Schwartz, "Sdp gaps and ugc hardness for multiway cut, 0-extension,and metric labeling," in STOC, 2008, pp. 11-20.
P. Raghavendra, "A Note on Yekhanin's Locally Decodable Codes," Electronic Colloquium on Computational Complexity (ECCC), vol. 14, no. 016, 2007.
Awards, Memberships and Fellowships
Michael and Sheila Held Prize, 2018Okawa Research Grant, 2015
NSF Faculty Early Career Development Award (CAREER), 2013
Sloan Research Fellow, 2012