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 J. Comput., vol. 40, no. 3, pp. 878-914, 2011.
• P. Gopalan, V. Guruswami, and P. Raghavendra, "List Decoding Tensor Products and Interleaved Codes," SIAM J. Comput., 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 J. Comput., 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.