2008
|
||
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
FOCS 2008
|
|
|
Towards Computing the Grothendieck constant
Prasad Raghavendra, David Steurer
Submitted
|
|
|
2007
|
||
A 3-Query PCP over Integers
Venkatesan Guruswami, Prasad Raghavendra
STOC 2007
|
|
|
Coarse Differentiation and Planar Multiflows
James Lee, Prasad Raghavendra
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
|
|
|
2006
|
||
Hardness of Learning Halfspaces with Noise
Venkatesan Guruswami, Prasad Raghavendra.
FOCS 2006
|
|
|
Undergraduate:
|
||
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
|
||