# Faculty Publications - Prasad Raghavendra

## Articles in journals or magazines

- Y. Azar, U. Feige, I. Gamzu, T. Moscibroda, and P. Raghavendra, "Buffer Management for Colored Packets with Deadlines,"
*Theory Comput. Syst.*, vol. 49, no. 4, pp. 738-756, 2011. - 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. - 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. - 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, "A Note on Yekhanin's Locally Decodable Codes,"
*Electronic Colloquium on Computational Complexity (ECCC)*, vol. 14, no. 016, 2007.

## Articles in conference proceedings

- 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. - A. Bhattacharyya, E. Grigorescu, P. Raghavendra, and A. Shapira, "Testing odd-cycle-freeness in Boolean functions," in
*SODA*, 2012, pp. 1140-1149. - V. Guruswami, Y. Makarychev, P. Raghavendra, D. Steurer, and Y. Zhou, "Finding Almost-Perfect Graph Bisections," in
*ICS*, 2011, pp. 321-337. - B. Barak, P. Raghavendra, and D. Steurer, "Rounding Semidefinite Programming Hierarchies via Global Correlation," in
*FOCS*, 2011, pp. 472-481. - A. Louis, P. Raghavendra, P. Tetali, and S. Vempala, "Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions," in
*APPROX-RANDOM*, 2011, pp. 315-326. - A. Louis, P. Raghavendra, P. Tetali, and S. Vempala, "Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions," in
*APPROX-RANDOM*, 2011, pp. 315-326. - P. Raghavendra and D. Steurer, "Graph expansion and the unique games conjecture," in
*STOC*, 2010, pp. 755-764. - P. Raghavendra, D. Steurer, and P. Tetali, "Approximations for the isoperimetric and spectral profile of graphs and related parameters," in
*STOC*, 2010, pp. 631-640. - I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Tan, "Bounding the average sensitivity and noise sensitivity of polynomial threshold functions," in
*STOC*, 2010, pp. 533-542. - E. Chlamtac, R. Krauthgamer, and P. Raghavendra, "Approximating Sparsest Cut in Graphs of Bounded Treewidth," in
*APPROX-RANDOM*, 2010, pp. 124-137. - P. Gopalan, V. Guruswami, and P. Raghavendra, "List decoding tensor products and interleaved codes," in
*STOC*, 2009, pp. 13-22. - Y. Azar, U. Feige, I. Gamzu, T. Moscibroda, and P. Raghavendra, "Buffer management for colored packets with deadlines," in
*SPAA*, 2009, pp. 319-327. - P. Raghavendra and D. Steurer, "Towards computing the Grothendieck constant," in
*SODA*, 2009, pp. 525-534. - T. S. Jayram, S. Kopparty, and P. Raghavendra, "On the Communication Complexity of Read-Once AC^0 Formulae," in
*IEEE Conference on Computational Complexity*, 2009, pp. 329-340. - 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. - 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. - V. Guruswami, R. Manokaran, and P. Raghavendra, "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph," in
*FOCS*, 2008, pp. 573-582. - V. Guruswami and P. Raghavendra, "Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness," in
*APPROX-RANDOM*, 2008, pp. 77-90. - V. Guruswami and P. Raghavendra, "A 3-query PCP over integers," in
*STOC*, 2007, pp. 198-206. - N. Chen, R. Engelberg, C. Nguyen, P. Raghavendra, A. Rudra, and G. Singh, "Improved Approximation Algorithms for the Spanning Star Forest Problem," in
*APPROX-RANDOM*, 2007, pp. 44-58. - J. R. Lee and P. Raghavendra, "Coarse Differentiation and Multi-flows in Planar Graphs," in
*APPROX-RANDOM*, 2007, pp. 228-241. - K. Srinathan, P. Raghavendra, and C. P. Rangan, "On Proactive Perfectly Secure Message Transmission," in
*ACISP*, 2007, pp. 461-473. - V. Guruswami and P. Raghavendra, "Hardness of Learning Halfspaces with Noise," in
*FOCS*, 2006, pp. 543-552.