Prasad Raghavendra

Research Areas

Theory (THY)

Research Centers

Center for the Theoretical Foundations of Learning, Inference, Information, Intelligence, Mathematics and Microeconomics at Berkeley (CLIMB)
Simons Institute for the Theory of Computing (SITC)

Teaching Schedule

Spring 2025

CS 294-284. Constraint Satisfaction Problems: Theories of Tractability, Fr 13:00-14:59, Soda 306
CS 298-2. Theory Seminar, We 12:00-13:29, Soda 438

Fall 2025

CS 298-2. Theory Seminar, We 12:00-13:29, Soda 438

Education

2009, PhD, Computer Science and Engineering, University of Washington, Seattle
2007, 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.