38 citations · 171 across the 26 of their papers we have counts for
5 papers · 1 filter
Many Sparse Cuts via Higher Eigenvalues
Anand Louis, Prasad Raghavendra, Prasad Tetali +1
Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset such that its expansion (a.k.a. conductance) is bounded as follows: \[ ϕ(S) \defeq \fra…
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more eff…
Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies
Prasad Raghavendra, Ning Tan
This work is concerned with approximating constraint satisfaction problems (CSPs) with an additional global cardinality constraints. For example, \maxcut is a boolean CSP where the…
Testing Odd-Cycle-Freeness in Boolean Functions
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra +1
Call a function f : F_2^n -> {0,1} odd-cycle-free if there are no x_1, ..., x_k in F_2^n with k an odd integer such that f(x_1) = ... = f(x_k) = 1 and x_1 + ... + x_k = 0. We show…
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…