|
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 |
|
|
|
Many sparse cuts via higher eigen-values Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala STOC 2012 |
|
|
|
Approximating CSPs with global cardinality constraints using SDP hierarchies Prasad Raghavendra, Ning Tan SODA 2012 |
|
|
|
Testing odd-cycle-freeness in boolean functions. Arnab Bhattacharya, Elena Grigorescu, Prasad Raghavendra, Assaf Shapira SODA 2012 |
|
|
|
Bypassing the UGC for some optimal geometric inapproximability results Venkatesan Guruswami,Prasad Raghavendra,Rishi Saket, Yi Wu SODA 2012 |
|
|
|
Rounding hierarchies with global correlation Boaz Barak, Prasad Raghavendra, David Steurer FOCS 2011 |
|
|
|
Reductions between Expansion Problems Prasad Raghavendra, Madhur Tulsiani, David Steurer Manuscript |
|
|
|
Finding almost-perfect graph bisections Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou ICS 2010 |
|
|
|
Approximating Sparsest Cut on Graphs of Bounded Treewidth Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra APPROX 2010 |
|
|
|
Graph Expansion and the Unique Games Conjecture Prasad Raghavendra, David Steurer STOC 2010 |
|
|
|
Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters Prasad Raghavendra, David Steurer, Prasad Tetali STOC 2010 |
|
|
|
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 |
|
|
|
List Decoding Tensor Products and Interleaved Codes. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra STOC 2009 |
|
|
|
Communication Complexity of Read-Once AC0 Formulae T.S.Jayram, Swastik Kopparty, Prasad Raghavendra CCC 2009 |
|
|
|
How to Round Any CSP Prasad Raghavendra, David Steurer FOCS 2009 |
|
|
|
Integrality Gaps for Strong SDP Relaxations of Unique Games Prasad Raghavendra, David Steurer FOCS 2009 |
|
|
|
Agnostic Learning of Monomials by Halfspaces is Hard Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu FOCS 2009 |
|
|
|
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 |
|
|
|
Towards Computing the Grothendieck Constant Prasad Raghavendra, David Steurer SODA 2009 |
|
|
|
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) |
|
|
|
SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension and Metric Labeling Rajsekar Manokaran, Seffi Naor, Prasad Raghavendra, Roy Schwartz STOC 2008 |
|
|
|
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 |
|
|
|
Beating the Random Ordering is Hard : Inapproximability of Maximum Acyclic Subgraph Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra STOC 2007, Invited to SICOMP Special Issue |
|
|
|
A 3-Query PCP over Integers Venkatesan Guruswami, Prasad Raghavendra Transactions of Computation Theory, (also in STOC 2007) |
|
|
|
Coarse Differentiation and Planar Multiflows James Lee, Prasad Raghavendra Discrete and Computational Geometry 2010 (preliminary version in APPROX 2007) |
|
|
|
A Note on Yekhanin's Locally Decodable Codes Prasad Raghavendra Electronic Colloqium on Computational Complexity ECCC TR07-016 |
|
|
|
Improved Approximation Algorithms for the Spanning Star Forest Problem Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh APPROX 2007 |
|
|
|
Hardness of Learning Halfspaces with Noise Venkatesan Guruswami, Prasad Raghavendra. FOCS 2006, SICOMP Special Issue for FOCS 2006 |
|
|
|
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 |