# Prasad Raghavendra - University of Washington

## Contact Details

NamePrasad Raghavendra |
||

AffiliationUniversity of Washington |
||

CitySeattle |
||

CountryUnited States |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Computational Complexity (18) Computer Science - Data Structures and Algorithms (13) Mathematics - Combinatorics (5) Computer Science - Discrete Mathematics (4) Computer Science - Learning (2) Mathematics - Optimization and Control (2) Mathematics - Metric Geometry (1) Mathematics - Information Theory (1) Computer Science - Information Theory (1) Computer Science - Artificial Intelligence (1) Computer Science - Distributed; Parallel; and Cluster Computing (1) |

## Publications Authored By Prasad Raghavendra

We present a simple distributed algorithm that, given a regular graph consisting of two communities (or clusters), each inducing a good expander and such that the cut between them has sparsity $1/\mbox{polylog}(n)$, recovers the two communities. More precisely, upon running the protocol, every node assigns itself a binary label of $m = \Theta(\log n)$ bits, so that with high probability, for all but a small number of outliers, nodes within the same community are assigned labels with Hamming distance $o(m)$, while nodes belonging to different communities receive labels with Hamming distance at least $m/2 - o(m)$. We refer to such an outcome as a "community sensitive labeling" of the graph. Read More

It has often been claimed in recent papers that one can find a degree d Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan O'Donnell notes this widely quoted claim is not necessarily true. He presents an example of a polynomial system with bounded coeffcients that admits low-degree proofs of non-negativity, but these proofs necessarily involve numbers with an exponential number of bits, causing the Ellipsoid algorithm to take exponential time. Read More

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results, previously, it was only known that linear programs of size $n^{o(\log n)}$ cannot beat random guessing for any CSP (Chan-Lee-Raghavendra-Steurer 2013). Read More

We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval. Read More

A $(k \times l)$-birthday repetition $\mathcal{G}^{k \times l}$ of a two-prover game $\mathcal{G}$ is a game in which the two provers are sent random sets of questions from $\mathcal{G}$ of sizes $k$ and $l$ respectively. These two sets are sampled independently uniformly among all sets of questions of those particular sizes. We prove the following birthday repetition theorem: when $\mathcal{G}$ satisfies some mild conditions, $val(\mathcal{G}^{k \times l})$ decreases exponentially in $\Omega(kl/n)$ where $n$ is the total number of questions. Read More

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when $m/n = \omega(1)$). Intuitively, strong refutation should become easier as the clause density $m/n$ grows, because the contradictions introduced by the random clauses become more locally apparent. Read More

We give a lower bound of $\tilde{\Omega}(\sqrt{n})$ for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erd\"os-R\'enyi graph $G(n,\tfrac{1}{2})$, with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of $\tilde{\Omega}(\sqrt{n})$, so that the program cannot distinguish between a random graph and a random graph with a planted clique of size $\tilde{O}(\sqrt{n})$. This bound is tight. Read More

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a $\frac{1}{2} + \Omega(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i. Read More

Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo{\ss} recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. Read More

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP {\Lambda} is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to {\Lambda} to create new ones. In an entirely separate line of work, the unique games conjecture yields a characterization of approximability of Max-CSPs. Read More

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e. Read More

Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved efficiently under the assumption that the unknown matrix is incoherent and the subsample is drawn uniformly at random. Are these assumptions necessary? It is well known that Matrix Completion in its full generality is NP-hard. Read More

In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness $\epsilon$ and soundness $\frac{1}{2}$ is at least as difficult as Small-Set Expansion with completeness $\epsilon$ and soundness $f(\epsilon)$, for any function $f(\epsilon)$ which grows faster than $\sqrt{\epsilon}$. We achieve this amplification via random walks -- our gadget is the graph with adjacency matrix corresponding to a random walk on the original graph. Read More

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8. Read More

We study the complexity of approximating the vertex expansion of graphs $G = (V,E)$, defined as \[ \Phi^V := \min_{S \subset V} n \cdot \frac{|N(S)|}{|S| |V \backslash S|}. \] We give a simple polynomial-time algorithm for finding a subset with vertex expansion $O(\sqrt{OPT \log d})$ where $d$ is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than $C\sqrt{OPT \log d}$ for an absolute constant $C$. Read More

Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K \subset V$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U, K-U $ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^{k}}$ for every graph with $k$ terminals. Read More

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. Read More

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 efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1. Read More

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 input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the numberof crossing edges, $|E(S,\bar S)|$. The \maxbisection problem is a variant of \maxcut with an additional global constraint that each side of the cut has exactly half the vertices, i. Read More

Call a function f : F_2^n -> {0,1} odd-cycle-free if there are no x_1, ... Read More

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 of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most \eps worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k\cdot\rank_{\geq \theta}(\Ins)/\poly(\e) \;, where k is the alphabet size of I, $\theta=\poly(\e/k)$, and $\rank_{\geq \theta}(\Ins)$ denotes the number of eigenvalues larger than $\theta$ in the normalized adjacency matrix of the constraint graph of $\Ins$. Read More

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)$ of the examples, it is NP-hard to find a halfspace that is correct on $(1/2+\eps)$ of the examples, for arbitrary constants $\eps > 0$. In learning theory terms, weak agnostic learning of monomials is hard, even if one is allowed to output a hypothesis from the much bigger concept class of halfspaces. This hardness result subsumes a long line of previous results, including two recent hardness results for the proper learning of monomials and halfspaces. Read More

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 graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique Games Conjecture (Raghavendra, Steurer, STOC 2010). Read More

We give the first constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the flow-cut gap and/or metric embeddings, our approach exploits the Sherali-Adams hierarchy of linear programming relaxations. Read More

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). These bounds hold both for PTFs over the Boolean hypercube and for PTFs over $\R^n$ under the standard $n$-dimensional Gaussian distribution. Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial \cite{GL:94}, which states that the symmetric function slicing the middle $d$ layers of the Boolean hypercube has the highest average sensitivity of all degree-$d$ PTFs. Read More

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 ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. Read More

**Affiliations:**

^{1}University of Washington,

^{2}University of Washington

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 class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from 3/2 to 2, yielding the first lower bound that doesn't follow from elementary calculations. Our approach uses the {\em coarse differentiation} method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into $L_1$. Read More