Prasad Raghavendra
Professor
Info Links
Research Areas
Research Centers
Teaching Schedule
Fall 2023
- CS 298-2. Theory Seminar, We 12:00-13:29, Soda 438
Spring 2024
- CS 170. Efficient Algorithms and Intractable Problems, TuTh 15:30-16:59, Li Ka Shing 245
- CS 298-2. Group Studies Seminars, or Group Research, 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.