activity
20082012
most citedAverage sensitivity and noise sensitivity of polynomial threshold functions

11 citations · 28 across the 5 of their papers we have counts for

collaborators
Showing 2008Show all

2 papers · 1 filter

cs.IT2008

List Decoding Tensor Products and Interleaved Codes

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for {\em every} code, the…

math.MG2008★ 7 cited

Coarse differentiation and multi-flows in planar graphs

James R. Lee, Prasad Raghavendra

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound Chakrabarti, Jaffe, Lee, and Vincent for this cla…