Phd Thesis: Approximating NP-hard problems: efficient algorithms and their limits image002 (5K)
Advised by Venkatesan Guruswami

Publications

Making the long code shorter, with applications to the unique games conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka,Prasad Raghavendra,David Steurer
Manuscript
image002 (5K)
Many sparse cuts via higher eigen-values
Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala
STOC 2012
image002 (5K)
Approximating CSPs with global cardinality constraints using SDP hierarchies
Prasad Raghavendra, Ning Tan
SODA 2012
image002 (5K)
Testing odd-cycle-freeness in boolean functions.
Arnab Bhattacharya, Elena Grigorescu, Prasad Raghavendra, Assaf Shapira
SODA 2012
image002 (5K)
Bypassing the UGC for some optimal geometric inapproximability results
Venkatesan Guruswami,Prasad Raghavendra,Rishi Saket, Yi Wu
SODA 2012
image002 (5K)
Rounding hierarchies with global correlation
Boaz Barak, Prasad Raghavendra, David Steurer
FOCS 2011
image002 (5K)
Reductions between Expansion Problems
Prasad Raghavendra, Madhur Tulsiani, David Steurer
Manuscript
image002 (5K)
Finding almost-perfect graph bisections
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
ICS 2010
image002 (5K)
Approximating Sparsest Cut on Graphs of Bounded Treewidth
Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
APPROX 2010
image002 (5K)
Graph Expansion and the Unique Games Conjecture
Prasad Raghavendra, David Steurer
STOC 2010
image002 (5K)
Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters
Prasad Raghavendra, David Steurer, Prasad Tetali
STOC 2010
image002 (5K) image002 (5K)
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
Ilias Diakonikolas,Prahlad Harsha, Adam Klivans, Raghuvardhan Meka, Prasad Raghavendra, Rocco Servedio, Li-Yang Tang
STOC 2010
image002 (5K)
List Decoding Tensor Products and Interleaved Codes.
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
STOC 2009
image002 (5K) image002 (5K)
Communication Complexity of Read-Once AC0 Formulae
T.S.Jayram, Swastik Kopparty, Prasad Raghavendra
CCC 2009
image002 (5K)
How to Round Any CSP
Prasad Raghavendra, David Steurer
FOCS 2009
image002 (5K) image002 (5K)
Integrality Gaps for Strong SDP Relaxations of Unique Games
Prasad Raghavendra, David Steurer
FOCS 2009
image002 (5K)
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
FOCS 2009
image002 (5K)
Buffer Management for Colored Packets with Deadlines
Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra
SPAA 2009, Invited to SPAA 2009 Special Issue
image002 (5K)
Towards Computing the Grothendieck Constant
Prasad Raghavendra, David Steurer
SODA 2009
image002 (5K)
Optimal Algorithms and Inapproximability Results for Every CSP?
Prasad Raghavendra
STOC 2008 (Co-winner of the Best Paper award and winner of the Best Student Paper award)
image002 (5K) image002 (5K)
SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension and Metric Labeling
Rajsekar Manokaran, Seffi Naor, Prasad Raghavendra, Roy Schwartz
STOC 2008
image002 (5K)
Constraint Satisfaction over Non Boolean Domain: Approximation Algorithms and Unique Games Hardness
Venkatesan Guruswami, Prasad Raghavendra
APPROX-2008, also on Electronic Colloqium on Computational Complexity ECCC TR-08-008
image002 (5K) image002 (5K)
Beating the Random Ordering is Hard : Inapproximability of Maximum Acyclic Subgraph
Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra
STOC 2007, Invited to SICOMP Special Issue
image002 (5K)
A 3-Query PCP over Integers
Venkatesan Guruswami, Prasad Raghavendra
Transactions of Computation Theory, (also in STOC 2007)
image002 (5K) image002 (5K)
Coarse Differentiation and Planar Multiflows
James Lee, Prasad Raghavendra
Discrete and Computational Geometry 2010 (preliminary version in APPROX 2007)
image002 (5K) image002 (5K)
A Note on Yekhanin's Locally Decodable Codes
Prasad Raghavendra
Electronic Colloqium on Computational Complexity ECCC TR07-016
image002 (5K)
Improved Approximation Algorithms for the Spanning Star Forest Problem
Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh
APPROX 2007
image002 (5K) image002 (5K)
Hardness of Learning Halfspaces with Noise
Venkatesan Guruswami, Prasad Raghavendra.
FOCS 2006, SICOMP Special Issue for FOCS 2006
image002 (5K) image002 (5K)
On the Optimal Communication Complexity of Multiphase Protocols for Perfect Communication
Kannan Srinathan, N. R. Prasad, C. Pandu Rangan
IEEE Symposium on Security and Privacy (IEEE-SP) 2007
On Proactive Perfectly Secure Message Transmission
Kannan Srinathan, Prasad Raghavendra, C. Pandu Rangan
Australasian Conference on Security and Privacy (ACISP) 2007