Prasad Raghavendra

Larger Photo

Professor

Contact Information

623 Soda Hall

prasad@cs.berkeley.edu

Office Hours

Wed 11-noon, 623 Soda

Links

Personal Homepage

Publications

Dissertations

Research Support

Eva Leach
eva.leach@berkeley.edu

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

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

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

CS 294-308. Semidefinite Programming and Sum-of-Squares Proofs, TuTh 15:30-16:59, Mulford 230

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.

Michael and Sheila Held Prize, 2018
Okawa Research Grant, 2015
NSF Faculty Early Career Development Award (CAREER), 2013
Sloan Research Fellow, 2012

Prasad Raghavendra: Faculty Home Page