Faculty Publications - Prasad Raghavendra

Articles in journals or magazines

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.