Arrow Research search

Author name cluster

Prasad Raghavendra

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

41 papers
1 author row

Possible papers

41

FOCS Conference 2025 Conference Paper

On optimal distinguishers for Planted Clique

  • Ansh Nagda
  • Prasad Raghavendra

In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a distinguishing algorithm is measured by its advantage, i. e. , its incremental probability of success over a random guess. A classic example of a distinguishing problem is the Planted Clique problem, where the input is a graph sampled from either $G(n, 1 / 2)$ - the standard Erdős-Rényi model, or $G(n, 1 / 2, k)$ the Erdős-Rényi model with a clique planted on a random subset of k vertices. The Planted Clique Hypothesis asserts that efficient algorithms cannot achieve advantage better than some absolute constant, say 1/4, whenever $k=n^{1 / 2-\Omega(1)}$. In this work, we aim to precisely understand the optimal distinguishing advantage achievable by efficient algorithms on Planted Clique. We show the following results under the Planted Clique hypothesis: •Optimality of low-degree polynomials: No efficient algorithm can beat the advantage the optimal low-degree polynomial. Concretely, this means that the advantage of any efficient algorithm is at most $(1+o(1)) \cdot k^{2} /(\sqrt{\pi} n)$, which is optimal in light of a simple edge-counting algorithm achieving this bound. •Harder planted distributions: There is an efficiently sampleable distribution ${\mathcal{P}}^{*}$ supported on graphs containing k cliques such that no efficient algorithm can distinguish ${\mathcal{P}}^{*}$ from $G(n, 1 / 2)$ with advantage $n^{-d}$ for an arbitrarily large constant d. In other words, there exist alternate planted distributions that are much harder than $G(n, 1 / 2, k)$. Along the way, we prove a constructive hard-core lemma for a broad class of distributions with respect to low-degree polynomials. This result is applicable much more widely beyond Planted Clique and might be of independent interest.

Details

FOCS Conference 2024 Conference Paper

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold

  • Venkatesan Guruswami
  • Jun-Ting Hsieh
  • Prasad Raghavendra

We consider the task of certifying that a random d-dimensional subspace X in $\mathbb{R}^{\gamma}$ is well-spread - every vec-tor $\chi\in X$ satisfies $c\sqrt{n}\Vert x\Vert_{2}\leq\Vert x\Vert_{1}\leq\sqrt{n}^{-}\Vert x\Vert_{2}$. In a seminal work, Barak et. al. [3] showed a polynomial-time certification algorithm when $d\leqslant O(\sqrt{n})$. On the other hand, when $d \gg \sqrt{n} r$ the certification task is information-theoretically possible but there is evidence that it is computationally hard [10], [39], a phenomenon known as the information-computation gap. In this paper, we give sub exponential-time certification algorithms in the $d \ll \sqrt{n}$ regime. Our algorithm runs in time $\exp(\tilde{O}(n^{\varepsilon}))$ when $\dot{d} \leqslant \widetilde{O}\left(n^{\frac{1+\varepsilon}{2}}\right)$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.

Details

FOCS Conference 2024 Conference Paper

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains

  • Kuikui Liu
  • Sidhanth Mohanty
  • Prasad Raghavendra
  • Amit Rajaraman
  • David X. Wu

Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can be shown to always converge quickly to measures that are locally stationary, i. e. , measures that don't change over a small number of steps. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures: 1)We show that Glauber dynamics on the hardcore model can be used to find large independent sets in triangle-free graphs of bounded degree. 2)We prove that Glauber dynamics on the Ising model defined by a spiked matrix model finds a vector with constant correlation with the planted spike. 3)We show that for sufficiently large constant signal-to-noise ratio, Glauber dynamics on the Ising model finds a vector that has constant correlation with the hidden community vector. In other words, Glauber dynamics subsumes the spectral method for spiked Wigner and community detection, by weakly recovering the planted spike. The full version of this paper can be found on arXiv(arXiv ID: 2405. 20849).

Details

STOC Conference 2023 Conference Paper

Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion

  • Ronen Eldan
  • Dan Mikulincer
  • Prasad Raghavendra

We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.

Details

SODA Conference 2021 Conference Paper

Local Statistics, Semidefinite Programming, and Community Detection

  • Jess Banks
  • Sidhanth Mohanty
  • Prasad Raghavendra

We propose a new, efficiently solvable hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into k communities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The problem of detection, where we are to decide with high probability whether a graph was drawn from this model or the uniform distribution on regular graphs, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold. In this work, we consider two models of random graphs namely the well-studied (irregular) Stochastic Block Model and a distribution over random regular graphs we'll call the Degree Regular Block Model. For both these models, we show that sufficiently high constant levels of our hierarchy can perform detection arbitrarily close to the KS threshold and that our algorithm is robust to up to a linear number of adversarial edge perturbations. Furthermore, in the case of Degree Regular Block Model, we show that below the Kesten-Stigum threshold no constant level can do so. In the case of the (irregular) Stochastic Block Model, it is known that efficient algorithms exist all the way down to this threshold, although none are robust to adversarial perturbation of a linear number of edges. More importantly, there is little complexity-theoretic evidence that detection is hard below the threshold. In the DRBM with more than two groups, it has not to our knowledge been proven that any algorithm succeeds down to the KS threshold, let alone that one can do so robustly, and there is a similar dearth of evidence for hardness below this point. Our SDP hierarchy is highly general and applicable to a wide range of hypothesis testing problems.

Details

FOCS Conference 2021 Conference Paper

On statistical inference when fixed points of belief propagation are unstable

  • Siqi Liu 0005
  • Sidhanth Mohanty
  • Prasad Raghavendra

Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a stochastic block model, the community labels are hidden variables that are to be recovered from the edges of the graph. Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where detection and recovery should be algorithmically tractable. At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing an input with a planted signal from one without; (ii) a general polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the hidden assignment significantly better than a random guess would. Analogous to the spectral algorithm for community detection [1], [2], the detection and recovery algorithms are based on the spectra of a matrix that arises as the derivatives of the belief propagation update rule. To devise a spectral algorithm in our general model, we obtain bounds on the spectral norms of certain families of random matrices with correlated and matrix valued entries. We then demonstrate how eigenvectors of various powers of the matrix can be used to partially recover the hidden variables.

Details

STOC Conference 2020 Conference Paper

Lifting sum-of-squares lower bounds: degree-2 to degree-4

  • Sidhanth Mohanty
  • Prasad Raghavendra
  • Jeff Xu

The degree-4 Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, Sparsest Cut, all MaxCSPs and tensor PCA. Despite being an explicit algorithm with relatively low computational complexity, the limits of degree-4 SoS SDP are not well understood. For example, existing integrality gaps do not rule out a (2−)-algorithm for Vertex Cover or a (0.878+)-algorithm for MaxCut via degree-4 SoS SDPs, each of which would refute the notorious Unique Games Conjecture. We exhibit an explicit mapping from solutions for degree-2 Sum-of-Squares SDP (Goemans-Williamson SDP) to solutions for the degree-4 Sum-of-Squares SDP relaxation on boolean variables. By virtue of this mapping, one can lift lower bounds for degree-2 SoS SDP relaxation to corresponding lower bounds for degree-4 SoS SDPs. We use this approach to obtain degree-4 SoS SDP lower bounds for MaxCut on random d -regular graphs, Sherington-Kirkpatrick model from statistical physics and PSD Grothendieck problem. Our constructions use the idea of pseudocalibration towards candidate SDP vectors, while it was previously only used to produce the candidate matrix which one would show is PSD using much technical work. In addition, we develop a different technique to bound the spectral norms of graphical matrices that arise in the context of SoS SDPs. The technique is much simpler and yields better bounds in many cases than the trace method – which was the sole technique for this purpose.

Details

SODA Conference 2019 Conference Paper

Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones

  • Prasad Raghavendra
  • Nick Ryder
  • Nikhil Srivastava
  • Benjamin Weitz

Hyperbolic programming is a generalization of semidefinite programming in which one optimizes over linear sections of hyperbolicity cones rather than semidefinite ones. It is not known whether this generalization is strict: the Generalized Lax Conjecture asks whether every hyperbolicity cone is a section of a semidefinite cone of sufficiently high dimension. We study a quantitative version of this question, and prove that the space of hyperbolicity cones of hyperbolic polynomials of degree d in n variables contains ( n / d ) Ω( d ) pairwise distant cones in the Hausdorff metric, implying that any semidefinite representation of such cones must have dimension at least ( n / d ) Ω( d ) (even allowing a small approximation error). The cones are perturbations of the hyperbolicity cones of elementary symmetric polynomials. Our proof contains several ingredients of independent interest, including the identification of a large subspace in which the elementary symmetric polynomials lie in the relative interior of the set of hyperbolic polynomials, and a quantitative generalization of the fact that a real-rooted polynomial with two consecutive zero coefficients must have a high multiplicity root at zero.

Details

FOCS Conference 2017 Conference Paper

The Power of Sum-of-Squares for Detecting Hidden Structures

  • Samuel B. Hopkins 0001
  • Pravesh K. Kothari
  • Aaron Potechin
  • Prasad Raghavendra
  • Tselil Schramm
  • David Steurer

We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: the twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables. We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program. Using related ideas on SoS algorithms and lowdegree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK + 16]), we prove a new SoS lower bound for the tensor PCA problem.

Details

SODA Conference 2016 Conference Paper

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

  • Samuel B. Hopkins 0001
  • Pravesh K. Kothari
  • Aaron Potechin
  • Prasad Raghavendra
  • Tselil Schramm

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log ( n ) added to an Erdős-Rényi graph, have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size. By contrast, information theoretically, one can recover planted cliques so long as ω ≫ log ( n ). In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [MPW15] and Deshpande and Montanari [DM15b]. Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless, improving upon the bound ω ≫ n 1/3 due to [DM15b]. 2. For, degree 2 d SoS does not recover the planted clique unless ω ≫ n 1/( d +1) /(2 d polylog n ), improving upon the bound due to [MPW15]. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works [MPW15, DM15b, FK03] by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev [Gri01a] An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of [MPW15, DM15b, FK03]

Details

STOC Conference 2015 Conference Paper

Lower Bounds on the Size of Semidefinite Programming Relaxations

  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

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., any spectrahedron) of dimension less than 2 n δ , for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for max-sat.

Details

FOCS Conference 2013 Conference Paper

Approximate Constraint Satisfaction Requires Large LP Relaxations

  • Siu On Chan
  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

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.

Details

FOCS Conference 2013 Conference Paper

The Complexity of Approximating Vertex Expansion

  • Anand Louis
  • Prasad Raghavendra
  • Santosh S. Vempala

We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as Φ V def = minSCV n. |N(S)|/(|S||V\S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(√(Φ V 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(√(Φ V log d)) for an absolute constant C. In particular, this implies for all constant ε > 0, it is SSE-hard to distinguish whether the vertex expansion <; ε or at least an absolute constant. The analogous threshold for edge expansion is √Φ with no dependence on the degree (Here Φ denotes the optimal edge expansion). Thus our results suggest that vertex expansion is harder to approximate than edge expansion. In particular, while Cheeger's algorithm can certify constant edge expansion, it is SSE-hard to certify constant vertex expansion in graphs.

Details

SODA Conference 2012 Conference Paper

Approximating CSPs with global cardinality constraints using SDP hierarchies

  • Prasad Raghavendra
  • Ning Tan 0002

This work is concerned with approximating constraint satisfaction problems (CSPs) with additional global cardinality constraints. For example, M ax C ut is a boolean CSP where the input is a graph G = ( V, E ) and the goal is to find a cut S ∪ Š = V that maximizes the number of crossing edges, | E ( S, Š )|. The Max Bisection problem is a variant of M ax C ut with a global constraint that each side of the cut has exactly half the vertices, i. e. , | S | = | V| /2. Several other natural optimization problems like M in B isection and approximating Graph Expansion can be formulated as CSPs with global cardinality constraints. In this work, we formulate a general approach towards approximating CSPs with global cardinality constraints using SDP hierarchies. To demonstrate the approach we present the following results: Using the Lasserre hierarchy, we present an algorithm that runs in time O ( n poly (1/ε) ) that given an instance of M ax B isection with value 1 − ε, finds a bisection with value 1 − O (√ε). This approximation is near-optimal (up to constant factors in O ()) under the Unique Games Conjecture. By a computer-assisted proof, we show that the same algorithm also achieves a 0. 85-approximation for M ax B isection, improving on the previous bound of 0. 70 (note that it is U nique G ames hard to approximate better than a 0. 878 factor). The same algorithm also yields a 0. 92-approximation for M ax 2-S at with cardinality constraints. For every CSP with a global cardinality constraints, we present a generic conversion from integrality gap instances for the Lasserre hierarchy to a dictatorship test whose soundness is at most integrality gap. Dictatorship testing gadgets are central to hardness results for CSPs, and a generic conversion of the above nature lies at the core of the tight Unique Games based hardness result for CSPs [Rag08].

Details

FOCS Conference 2012 Conference Paper

Making the Long Code Shorter

  • Boaz Barak
  • Parikshit Gopalan
  • Johan Håstad
  • Raghu Meka
  • Prasad Raghavendra
  • David Steurer

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) For any ε >; 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - ε, but G's adjacency matrix has more than exp(log δ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K polylog(K), improving over the previously known gadget with blowup of 2 Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

Details

MFCS Conference 2011 Invited Paper

Generic Techniques to Round SDP Relaxations

  • Prasad Raghavendra

Abstract This talk will survey two general approaches to rounding solutions to SDP relaxations. ‘Squish and Solve’ Rounding: This technique of rounding SDPs for constraint satisfaction problems generalizes and unifies a large body of SDP-based algorithms for CSPs. More specifically, it yields a a generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The generic algorithm is guaranteed to achieve an approximation ratio equal to the integrality gap of an SDP relaxation known to be optimal under Unique Games Conjecture. This is based on joint work with David Steurer. Rounding Using Correlations: Despite the numerous applications of semidefinite programming, in all but very few cases, the algorithms rely on arguably the simplest SDP relaxation. Hence the power of stronger semidefinite programming relaxations is not yet harnessed, leaving open the possibility that fundamental optimization problems like MaxCut and Vertex Cover could be approximated better using SDPs. The dearth of algorithms based on stronger SDP relaxations stems from the lack of general techniques to round these relaxations. In this work, we present a technique to round SDP hierarchies using the underlying correlations between variables. To demonstrate the technique, we present two applications of the technique, one to the problem of MaxBisection and other to general 2-CSPs on random graphs. This is based on joint works with David Steurer, Ning Tan and Boaz Barak.

Details

FOCS Conference 2011 Conference Paper

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 of the in- put 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 3, a rounding algorithm for r rounds of the Lasserre SDP hierarchy for 3 that obtains an integral solution which is at most ε worse than the relaxation's value (normalized to lie in [0, 1]), as long as r >; k·rank ≥θ (3)/ poly(ε), where k is the alphabet size of J, θ = poly(ε/k), and rank ≥θ (J) denotes the number of eigenvalues larger than θ in the normalized adjacency matrix of the constraint graph of J. In the case that J is a Unique Games instance, the threshold θ is only a polynomial in ε, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for every instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the nol O(r) constraints specified by the r th level of the Lasserre hierarchy, and in some cases r rounds of our program can be evaluated in time 2 O(r) poly(n).

Details

STOC Conference 2010 Conference Paper

Graph expansion and the unique games conjecture

  • Prasad Raghavendra
  • David Steurer

The edge expansion of a subset of vertices S ⊆ V in a graph G measures the fraction of edges that leave S. In a d-regular graph, the edge expansion/conductance Φ(S) of a subset S ⊆ V is defined as Φ(S) = (|E(S, V\S)|)/(d|S|). Approximating the conductance of small linear sized sets (size δ n) is a natural optimization question that is a variant of the well-studied Sparsest Cut problem. However, there are no known algorithms to even distinguish between almost complete edge expansion (Φ(S) = 1-ε), and close to 0 expansion. In this work, we investigate the connection between Graph Expansion and the Unique Games Conjecture. Specifically, we show the following: We show that a simple decision version of the problem of approximating small set expansion reduces to Unique Games. Thus if approximating edge expansion of small sets is hard, then Unique Games is hard. Alternatively, a refutation of the UGC will yield better algorithms to approximate edge expansion in graphs. This is the first non-trivial "reverse" reduction from a natural optimization problem to Unique Games. Under a slightly stronger UGC that assumes mild expansion of small sets, we show that it is UG-hard to approximate small set expansion. On instances with sufficiently good expansion of small sets, we show that Unique Games is easy by extending the techniques of [4].

Details

FOCS Conference 2009 Conference Paper

Agnostic Learning of Monomials by Halfspaces Is Hard

  • Vitaly Feldman
  • Venkatesan Guruswami
  • Prasad Raghavendra
  • Yi Wu 0002

We prove the following strong hardness result for learning: Given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with (1-¿)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 + ¿)-fraction of the examples, for arbitrary constant ¿ > 0. In learning theory terms, weak agnostic learning of monomials by halfspaces is NP-hard. This hardness result bridges between and subsumes two previous results which showed similar hardness results for the proper learning of monomials and halfspaces. As immediate corollaries of our result, we give the first optimal hardness results for weak agnostic learning of decision lists and majorities. Our techniques are quite different from previous hardness proofs for learning. We use an invariance principle and sparse approximation of halfspaces from recent work on fooling halfspaces to give a new natural list decoding of a halfspace in the context of dictatorship tests/label cover reductions. In addition, unlike previous invariance principle based proofs which are only known to give Unique Games hardness, we give a reduction from a smooth version of Label Cover that is known to be NP-hard.

Details

FOCS Conference 2009 Conference Paper

How to Round Any CSP

  • Prasad Raghavendra
  • David Steurer

A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work by one of the authors (STOC 2008) identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently (FOCS 2009), the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e. g. , in the fashion of Sherali-Adams LP hierarchies). In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and it also achieves the gap of much stronger SDP relaxations). The SDP relaxation we consider is stronger or equivalent to any relaxation used in literature to approximate CSPs. Thus, irrespective of the truth of the UGC, our work yields an efficient generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle. A common theme of this paper and the subsequent paper in the same conference is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by "smoothing'' without changing the objective value significantly.

Details

FOCS Conference 2009 Conference Paper

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  • Prasad Raghavendra
  • David Steurer

With the work of Khot and Vishnoi as a starting point, we obtain integrality gaps for certain strong SDP relaxations of Unique Games. Specifically, we exhibit a Unique Games gap instance for the basic semidefinite program strengthened by all valid linear inequalities on the inner products of up to exp(¿(log log n) 1/4 ) vectors. For a stronger relaxation obtained from the basic semidefinite program by R rounds of Sherali-Adams liftand-project, we prove a Unique Games integrality gap for R = ¿(log log n) 1/4. By composing these SDP gaps with UGC-hardness reductions, the above results imply corresponding integrality gaps for every problem for which a UGC-based hardness is known. Consequently, this work implies that including any valid constraints on up to exp(¿(log log n) 1/4 ) vectors to natural semidefinite program, does not improve the approximation ratio for any problem in the following classes: constraint satisfaction problems, ordering constraint satisfaction problems and metric labeling problems over constant-size metrics. We obtain similar SDP integrality gaps for Balanced Separator, building on. We also exhibit, for explicit constants ¿, ¿ > 0, an n-point negative-type metric which requires distortion ¿(log log n) ¿ to embed into ¿ 1, although all its subsets of size exp(¿(log log n) ¿ ) embed isometrically into ¿ 1.

Details

STOC Conference 2009 Conference Paper

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. (1) We show that for 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. (2) We show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur.et.al, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). (3)Using the notion of generalized Hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain tight list size bounds for small fields. Our results give better bounds on the list decoding radius than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson bound.

Details

SODA Conference 2009 Conference Paper

Towards computing the Grothendieck constant

  • Prasad Raghavendra
  • David Steurer

The Grothendieck constant K G is the smallest constant such that for every d ∊ ℕ and every matrix A = ( a ij ), where B ( d ) is the unit ball in ℝ d. Despite several efforts [15, 23], the value of the constant K G remains unknown. The Grothendieck constant K G is precisely the integrality gap of a natural SDP relaxation for the K M, N -Quadratic Programming problem. The input to this problem is a matrix A = ( α ij ) and the objective is to maximize the quadratic form Σ ij a ij x i y j over x i, y j ∊ [–1, 1]. In this work, we apply techniques from [22] to the K M, N -Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the K M, N -Q uadratic P rogramming problem to any factor better than the Grothendieck constant K G. By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: • An approximation algorithm for K M, N -Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant K G (optimal approximation ratio assuming the Unique Games Conjecture). • We show that the Grothendieck constant K G can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η -close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.

Details

FOCS Conference 2008 Conference Paper

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

  • Venkatesan Guruswami
  • Rajsekar Manokaran
  • Prasad Raghavendra

We prove that approximating the max. acyclic subgraph problem within a factor better than 1/2 is unique games hard. Specifically, for every constant epsiv > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsiv) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + epsiv) of its edges, then the UGC is false. Note that it is trivial to find an acyclic subgraph with 1/2 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The existence of a rho-approximation algorithmfor rho > 1/2 has been a basic open problem for a while. Our result is the first tight inapproximability result for an ordering problem. The starting point of our reduction isa directed acyclic subgraph (DAG) in which every cut isnearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed by Charikar et al. Using this, we are able to study max. acyclic subgraph, which is a constraint satisfaction problem (CSP) over an unbounded domain, by relating it to a proxy CSP over a bounded domain. The latter is then amenable to powerful techniques based on the invariance principle. Our results also give a super-constant factor inapproximability result for the feedback arc set problem. Using our reductions, we also obtain SDP integrality gapsfor both the problems.

Details

STOC Conference 2007 Conference Paper

A 3-query PCP over integers

  • Venkatesan Guruswami
  • Prasad Raghavendra

A classic result due to Haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field F q where each equation depends on exactly 3 variables and at least a fraction (1-ε) of the equations can be satisfied, it is NP-hard to satisfy even a fraction (1/q+ε) of the equations. In this work, we prove the analog of Håstad's result for equations over the integers (as well as the reals). Formally, we prove that for every ε,δ > 0, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is NP-hard to distinguish between the following two cases: (i) There is an assignment of integer values to the variables that satisfies at least a fraction (1-ε) of the equations, and (ii) No assignmenteven of real values to the variables satisfies more than a fraction δ of the equations.

Details

FOCS Conference 2006 Conference Paper

Hardness of Learning Halfspaces with Noise

  • Venkatesan Guruswami
  • Prasad Raghavendra

Learning an unknown halfspace (also called a perceptron) from, labeled examples is one of the classic problems in machine learning. In the noise-free case, when a half-space consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction (1 - epsiv) of the examples exists (for some small constant epsiv > 0), it was not known how to efficiently find a halfspace that is correct on even 51% of the examples. Nor was a hardness result that ruled out getting agreement on more than 99. 9% of the examples known. In this work, we close this gap in our understanding, and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary epsiv, delta > 0, we prove that given a set of examples-label pairs from the hypercube a fraction (1 - epsiv) of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction (frac12 + delta) of the examples. The hardness result is tight since it is trivial to get agreement on frac12 the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by Blum et. al in their work on learning halfspaces in the presence of random classification noise (A. Blum et. al, 1996), and in some more recent works as well. Along the way, we also obtain a strong hardness for another basic computational problem: solving a linear system over the rationals

Details