Goemans showed that any @math points @math in @math -dimensions satisfying @math triangle inequalities can be embedded into @math , with worst-case distortion at most @math . We extend this to the case when the points are approximately low-dimensional, albeit with average distortion guarantees. More precisely, we give an @math -to- @math embedding with average distortion at most the stable rank, @math , of the matrix @math consisting of columns @math . Average distortion embedding suffices for applications such as the Sparsest Cut problem. Our embedding gives an approximation algorithm for the problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on @math metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion @math . Furthermore, while the seminal result of Arora, Rao and Vazirani giving a @math guarantee for Uniform Sparsest Cut can be seen to imply Goemans' theorem with average distortion, our work opens up the possibility of proving such a result directly via a Goemans'-like theorem.
We recall that the best known upper bound for the worst-case distortion of embedding @math is @math @cite_11 @cite_5 , while the best known lower bound is @math for worst-case distortion @cite_18 , and @math for average distortion @cite_7 . Guarantees to on graphs were obtained using higher levels of the Lasserre hierarchy for SDPs @cite_12 @cite_13 . In contrast, a previous work of the first and third author @cite_17 showed weaker guarantees, but using just the basic SDP relaxation. Oveis Gharan and Trevisan @cite_6 also give a rounding algorithm for the basic SDP relaxation on low-threshold rank graphs, but require a stricter pre-condition on the eigenvalues ( @math ), and leverage it to give a stronger @math -approximation guarantees. Their improvement comes from a new structure theorem on the SDP solutions of low threshold-rank graphs being clustered, and using the techniques in ARV for analysis.
@cite_18 @cite_7 @cite_17 @cite_6 @cite_5 @cite_13 @cite_12 @cite_11
2949393806 2012238497 2216459995 2031923588
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 worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for 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 @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into ℝ d , where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n 1 12 is NP-hard. From this result we derive inapproximability with a factor roughly n 1 (22d-10) for every fixed d ≥ 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala), For d > 3, we obtain a stronger inapproximability result by a different reduction: assuming P≠NP, no polynomial-time algorithm can distinguish between spaces embeddable in ℝ d with constant distortion from spaces requiring distortion at least n c d , for a constant c > 0. The exponent c d has the correct order of magnitude, since every n-point metric space can be embedded in ℝ d with distortion O(n 2 d log 3 2 n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in ℝ 2 , while all not too large subspaces of it embed almost isometrically. Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing over the set of positive semidefinite matrices X with diagonal entries X_ii=1. We prove that for large (bounded) average degree d, the value of this semidefinite program (SDP) is --with high probability-- 2n*sqrt(d) + n, o(sqrt(d))+o(n). For a random regular graph of degree d, we prove that the SDP value is 2n*sqrt(d-1)+o(n), matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size n 2, with edge probability a n (within group) and b n (across). We prove that SDP detects the partition with high probability provided (a-b)^2 (4d)> 1+o_d(1), with d= (a+b) 2. By comparison, the information theoretic threshold for detecting the hidden partition is (a-b)^2 (4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new 'higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices. 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 2nδ, 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.