11 citations · 18 across the 3 of their papers we have counts for
6 papers
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum…
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra +1
We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$…
Reductions Between Expansion Problems
Prasad Raghavendra, David Steurer, Madhur Tulsiani
The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in gr…
Average sensitivity and noise sensitivity of polynomial threshold functions
Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio +1
We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree- polynomial threshold functions (PTFs). These bounds hold both for PTFs ove…
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…
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…