PaperlayerView exact revision on arXiv

Source-linked AI summary

Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, David Steurer

arXiv:1104.4680v1cs.DScs.CC

TL;DR

The paper addresses how to round SDP-hierarchy vector solutions into integral solutions while exploiting the input graph’s spectrum. It introduces global-correlation rounding for 2-CSPs and proves threshold-rank-based guarantees, including alphabet-independent thresholds and worst-case sublinear-round results for Unique Games. The implementation can require less than the full hierarchy and run in time 2^O(r) poly(n).

  • Problem

    High SDP-hierarchy levels are natural candidates for improving basic relaxations, but few higher-level algorithms were known, especially for problems related to the Unique Games Conjecture.

  • Method

    The paper combines global correlations in high-dimensional SDP solutions with hierarchy constraints to round vector solutions into integral assignments for 2-CSPs.

  • Results

    For Max 2-CSPs, r ≥ k · rank_≥τ(ℑ)/ε^c rounds achieve an assignment within ε of the relaxation; for Unique Games, τ is independent of k and worst-case small-root round bounds hold.

  • Takeaways & Limitations

    The approach matches the worst-case performance of the recent subexponential Unique Games algorithm while running faster on natural low-threshold-rank instance families.

  • Takeaways & Limitations

    Beyond Small-Set Expansion, the authors do not know how to transfer the Unique Games algorithms to other computational problems, leaving Max Cut as an open direction.

Abstract

from arXiv · show

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 θ}(\Ins)/\poly(\e) \;, where k is the alphabet size of I, $θ=\poly(\e/k)$, and $\rank_{\geq θ}(\Ins)$ denotes the number of eigenvalues larger than $θ$ in the normalized adjacency matrix of the constraint graph of $\Ins$. In the case that $\Ins$ is a \uniquegames instance, the threshold $θ$ is only a polynomial in $\e$, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for \emph{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 $n^{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)$.

1 Introduction

The paper introduces a spectrum-aware method for rounding SDP-hierarchy solutions and applies it to 2-CSPs, with guarantees governed by the constraint graph’s threshold rank. For Unique Games, the threshold can be independent of alphabet size, worst-case sublinear-round guarantees are available, and implementation can be faster than the full hierarchy.

  • 1 Introduction: SDP hierarchies tighten convex relaxations through successive rounds, but exploiting high levels for new algorithms has been difficult.Prior work more often established that high hierarchy levels do not help than used them algorithmically.
  • 1.1 Our results: The method uses global correlations in high-dimensional SDP solutions together with hierarchy constraints to improve rounding into integral solutions.It targets Max 2-CSPs and is faster than previously known algorithms on a natural family of instances.
  • 1.1 Our results: r ≥ k · rank_≥τ(ℑ)/ε^c rounds suffice for every Max 2-CSP instance to obtain an assignment within ε of the relaxation value.The threshold rank counts normalized-adjacency eigenvalues larger than τ, and the rounding scheme runs in polynomial time given an optimal SDP solution.
  • 1.1 Our results: For Unique Games, τ = ε^c is independent of alphabet size, while the required rank condition is rank_≥τ(ℑ) ≤ ε^(cr/k).The resulting assignment has value greater than v − ε.
  • 1.1 Our results: For (1 − ε)-satisfiable Unique Games, r ≥ ck · min{n^(cε^(1/3)), rank_≥1−cε(ℑ)} rounds suffice to achieve value greater than 1/2.Thus a sublinear, small-root number of rounds suffices in the worst case, regardless of threshold rank.
  • 1.1 Our results: The algorithm uses relaxed constraints and sufficiently many random variable sets, allowing r rounds to be implemented in time 2^O(r) poly(n) rather than n^O(r).The approach is related to subspace-enumeration algorithms but can use less than the full Lasserre hierarchy.

2 Our techniques

The paper rounds SDP-hierarchy vector solutions by exploiting global correlations and low-dimensional structure, with threshold rank connecting local correlations to global ones.

  • Rounding SDP’s using global correlation: Global correlation in the SDP vectors enables rounding to an integral solution using relatively few hierarchy rounds.The method combines global correlations with hierarchy constraints to improve rounding quality.
  • Rounding SDP’s using a small basis: A small basis of vectors can support high-quality Max Cut rounding when every solution vector has a sufficiently large projection into its span.With r + 2 hierarchy rounds and projection ρ sufficiently close to 1, the basis vectors can effectively be treated as one-dimensional.
  • Local to global correlation: Small threshold rank makes local correlation imply global correlation, supporting the existence of a useful low-dimensional basis.This condition applies to many natural instance families, including canonical hard instances based on noisy Gaussian graphs or noisy Boolean cubes.
  • Distribution view of SDP’s: The rounding process can be viewed distributionally: consistent local assignments are conditioned on selected basis-variable values.When local correlations persist, conditioning reduces uncertainty; when they disappear, independent sampling approximately preserves typical edge behavior.
  • Threshold rank vs global correlation: Threshold-rank and SDP approaches differ in robustness, because isolated vertices can increase eigenvalue counts without substantially changing local-to-global correlation or the Goemans-Williamson value.The paper presents this as a robustness advantage of SDP-based methods over spectral techniques.

Organization

The paper develops its results from formal definitions through a Max Cut low-rank warmup, general 2-CSP algorithms, local-to-global correlation, and implementation in weaker hierarchies.

  • Organization: The paper introduces notation and definitions before presenting Max Cut, general 2-CSP, correlation, and implementation sections in sequence.The organization follows the progression from a warmup algorithm to the general approach and its efficient implementation.

3 Preliminaries

This section defines the probabilistic, graph-theoretic, and Lasserre-hierarchy objects used throughout the paper, including local distributions and their consistency.

  • Notation and probability: Random variables use capital letters, assignments use lowercase letters, and variables in this work range over [k].For [k]-valued variables, Xa denotes the indicator that X equals a.
  • Notation and probability: Variance and collision probability are defined for [k]-valued random variables, with collision probability computed using an independent copy.The section states that these two quantities are related.
  • Notation and probability: Conditional variance denotes the expected variance of X after conditioning on the values of a jointly distributed variable Y.The notation is introduced for later variance-reduction arguments.
  • Unique Games: A Unique Games instance comprises a graph, label set, and edge-specific bijections, with the objective of maximizing satisfied edges.A labeling satisfies an edge when its endpoint labels obey that edge’s bijection.
  • Local distributions: An m-local distribution assigns labels to sets of at most m + 2 vertices, and a collection is consistent when overlapping sets agree on their marginals.The paper represents these distributions as m-local random variables.
  • Lasserre solutions: An m-round Lasserre solution contains consistent m-local random variables and vectors indexed by small vertex sets and local assignments.Feasibility requires consistency between the local random variables and the corresponding vectors, followed by an objective-maximization condition.
  • Lasserre solutions: For sets of at most m vertices and local assignments, the associated vectors induce a matrix used as a structural consequence of the Lasserre representation.The passage introduces this matrix property without displaying its full expression.
  • Local distributions: The text clarifies that conditioning on a local assignment produces [k]-valued conditional random variables.This clarification concerns the range of the variables after conditioning.

4 Warmup – MaxCut Example

The Max Cut warmup explains how local correlations among SDP-induced variables become global correlations, enabling variance reduction through conditioning and eventual rounding.

  • Max Cut formulation: Max Cut seeks a vertex partition maximizing the number of crossing edges.The objective is the fraction of graph edges crossing the cut.
  • SDP and local distributions: The Goemans-Williamson relaxation assigns unit vectors whose edge distances encode the SDP objective.For one-dimensional vectors in {±1}, the vector solution exactly represents a cut.
  • SDP and local distributions: Lasserre hierarchies provide consistent distributions on local assignments, but these variables are not jointly distributed across all vertices.Therefore, jointly sampling all variables while preserving every edge distribution is not directly possible.
  • Independent and correlated sampling: Independent sampling succeeds on edges where local distributions are close to products of marginals; deviations are measured by covariance and called local correlations.For two variables, covariance is defined as E[XiXj] − E[Xi]E[Xj].
  • Conditioning and variance reduction: Conditioning on one variable reduces the variance of correlated variables, providing a mechanism for progressively simplifying the local distributions.The expected reduction is obtained by choosing a vertex uniformly at random.
  • Local-to-global correlation: On regular graphs, edge correlations imply a lower bound on global correlation governed by the number of adjacency eigenvalues above a threshold.The relevant quantity rank⩾ρ(G) counts normalized adjacency eigenvalues larger than ρ.
  • Local-to-global correlation: The covariance matrix is positive semidefinite and can be represented through vectors, allowing the correlation argument to operate on vectorized SDP quantities.The construction uses vectors ui with inner products equal to covariances and then considers vi = ui⊗2.

5 General 2-CSP on Low Rank Graphs

The section develops propagation sampling for general Max 2-CSPs, using local-to-global correlation and conditional-variance reduction on low-threshold-rank constraint graphs. This yields Lasserre-rounding guarantees whose required rounds scale with alphabet size, error, and threshold rank.

  • Local-to-global correlation: Low threshold rank turns correlation across graph edges into global correlation among the associated vectors.The global-correlation lower bound depends on rank⩾ρ(G), the number of adjacency eigenvalues above ρ.
  • Variance reduction: Conditioning on a random vertex decreases typical variances whenever independent and correlated edge sampling differ substantially.The proof relates covariance squared divided by conditional variance to variance decrement, then connects vector inner products to these pairwise correlations.
  • Propagation Sampling: Propagation Sampling converts r-local random variables into a global distribution by randomly selecting seed vertices, sampling their labels, and conditionally sampling every other vertex.The algorithm chooses m uniformly from {1,…,r}, samples m seed vertices, then propagates labels using conditioned local distributions.
  • General 2-CSP guarantee: r ≫ O(k/ε^4) · rank⩾Ω(ε/k)^2(G) ensures the average sampling error is at most ε under the theorem’s positive-semidefiniteness assumptions.A decreasing potential can sustain large error for only O(k/ε^3)·rank⩾Ω(ε/k)^2(G) conditioning levels.
  • Unique Games specialization: For Unique Games, the threshold-rank dependence improves to r = k · rank⩾Ω(ε^4)(G)/ε^O(1), with the threshold independent of k.The corresponding rounding output has expected value at least σ − ε.

6 Local Correlation implies Global Correlation in Low-Rank Graphs

This section establishes a spectral relationship between local and global vector correlation. If vectors exhibit strong local correlation but weak global correlation, the graph must have many eigenvalues near one.

  • Spectral setup: For a regular graph, threshold rank counts normalized-adjacency eigenvalues exceeding a specified threshold.The graph is represented by a symmetric stochastic matrix with eigenvalues in [−1,1].
  • Local versus global correlation: A violation of the local-to-global correlation condition implies high threshold rank.The converse construction shows that many eigenvalues close to one support vectors with high local and low global correlation.
  • Spectral consequence: If vectors have the stated correlation pattern, then λ_(1−1/C)m ≥ 1 − C·ε for every C > 1, and in particular λ_m/2 > 1 − 2ε.The result is obtained by representing the vector Gram matrix in the graph’s eigenbasis and bounding spectral mass.
  • Converse construction: If m eigenvalues satisfy λ_m ≥ 1 − ε, there are vertex vectors with high local correlation and low global correlation.The vectors are built from orthonormal eigenfunctions associated with eigenvalues above 1−ε.

7 On Low Rank Approximations to Sets of Vectors

The section proves that a small subset of vectors can be used as a basis whose orthogonal complement has low average squared correlation. An iterative projection argument constructs such a subset using at most 1/ε vectors.

  • Low-rank approximation: For unit-ball vectors, a subset U of size at most 1/ε exists such that projected vectors have average normalized squared inner product at most ε.The projections are taken onto the orthogonal complement of the span of U.
  • Iterative construction: The construction iteratively selects a normalized vector from the current collection and projects all vectors onto its orthogonal complement.Each iteration reduces the typical squared norm by a quantified amount, and the process runs for 1/ε iterations.
  • Iterative construction: After the iterations, the selected vectors form an orthonormal basis for the span of U, and the remaining projections satisfy the target correlation bound.The argument tracks projected vectors through every iteration before applying nonnegativity of the final correlation expression.
  • Generalized projectors: The generalized theorem allows each subset U to specify an arbitrary projector onto a subspace orthogonal to U’s span.The same size and correlation guarantee remains valid even when the projector is not the full orthogonal-complement projector.

8 Rounding SDP Solutions to Unique Games

The section applies propagation rounding to Unique Games by combining local distributions, vector projections, and low-rank structure. Small seed sets make most variables nearly determined and preserve the SDP value up to controlled error.

  • Hierarchy and rounding: The hierarchy stores consistent local distributions, orthogonal label vectors, and SDP constraints matching their inner products to local probabilities.Its objective minimizes violated constraints, while propagation rounding samples labels from distributions conditioned on seed assignments.
  • Hierarchy and rounding: Propagation rounding samples seed labels and then independently samples each remaining vertex from its conditioned local distribution.For a seed set S, the method uses µS and the conditional distributions µS,t | xS.
  • Seed sets: A small seed set can make propagation rounding’s distribution close to the local distribution on any small target set.The closeness follows when the seed variables nearly determine the target variables.
  • Seed sets: For every m, a seed set S of size k^2m exists whose associated projections have low global correlation.The construction applies the low-rank approximation theorem to label vectors and projectors orthogonal to seed-associated vectors.
  • Variance and projections: Conditioning variance is bounded by squared lengths of projected SDP vectors, linking seed-set projections to determination of remaining variables.Lemma 8.3 bounds Var[X_i|X_S] using projections onto the complement of seed-vector spans.
  • Algorithmic consequences: For value 1−η Unique Games, an m-parameter algorithm runs in n^O(mk^2) time and finds a labeling satisfying 1−O(η/λ_m) of edges.Here λ_m is the mth smallest eigenvalue of the constraint graph’s Laplacian.
  • Algorithmic consequences: k^2m + 2 rounds support an algorithm that rounds Unique Games through propagation sampling over seed sets of size k^2m.The algorithm solves the corresponding Lasserre SDP and runs propagation rounding from every possible seed set.

Conclusions

The conclusions identify open questions about when SDP hierarchies work well, how their round complexity relates to computation time, and how Unique Games methods might transfer to other problems.

  • Unique Games: n^O(ε1/3) hierarchy rounds suffice for Unique Games on (1−ε)-satisfiable instances.The algorithm runs in 2^O(r) time rather than n^O(r), complicating the interpretation of hierarchy lower bounds as superpolynomial-time barriers.
  • Open directions: Unique Games algorithms are not known to translate to other computational problems except Small-Set Expansion.The authors mention improved 3-coloring algorithms as evidence that such combinations may nevertheless be possible.
  • Open directions: A clean characterization of 2-CSP instances where SDP hierarchies perform well remains open, including low-threshold-rank and planar graphs.The authors also ask for a corresponding low-threshold-rank generalization to k-CSPs with k > 2.

A Faster Algorithms for SDP hierarchies

The faster-hierarchy approach converts the rounding algorithm into a separation oracle, allowing weaker hierarchy solutions to be handled in time 2^O(r) poly(n).

  • Separation oracle: A separation oracle can compute a near-optimal m-round solution for weaker SDP hierarchies in 2^O(r) poly(n) time.The argument uses the equivalence between optimization and separation.
  • Rounding procedure: The Unique Games rounding algorithm selects a vertex set from SDP vectors, samples labels there, then propagates labels conditionally to the remaining vertices.The selected set depends only on SDP vectors, not on the local distributions unavailable to the oracle.
  • Oracle construction: The oracle begins by selecting a vertex subset using Theorem 7.1 and the supplied SDP vectors.This is the first step in extracting the oracle from the rounding algorithm.
  • Oracle construction: Linear programming finds local distributions consistent with the SDP inner products; mismatch either permits rounding or yields a violated valid linear constraint.Thus the oracle either supports a good assignment or separates the candidate vector solution.

B Omitted proofs from Section 5 and Section 8

The omitted proofs establish high local correlation by projecting and tensorizing SDP vectors, then relate these correlations to distances and variances through standard identities.

  • Section 8 proofs: The high-local-correlation lemma starts from an SDP solution for a Unique Games instance of value 1−η.Its proof uses projections of SDP vectors and preserves orthogonality across distinct labels.
  • Section 8 proofs: Tensorized projected vectors remain orthogonal for distinct labels and retain correlation across Unique Games constraints.The proof bounds tensor-product distances using component distances and the identity relating vector norms to normalized-vector distances.
  • Section 8 proofs: Distances between vertex-level vectors across graph edges are related to distances between label vectors under the corresponding constraint permutation.This completes the proof strategy for transferring local label correlations to the instance graph.
  • Section 5 proofs: The variance lemma represents indicator variables of r-local random variables through covariance vectors and normalized SDP vectors.The construction adds a shared orthogonal unit vector and verifies that the resulting vertex vectors lie in the unit ball.
  • Section 5 proofs: The variance proof uses orthogonality of distinct-label vectors to control inner products and distances between the constructed vectors.The displayed bounds combine lower and upper inner-product estimates with Cauchy–Schwarz.

C Facts about Variance

The variance appendix interprets conditional expectation as orthogonal projection and derives variance identities from that projection, including the binary-variable case.

  • Projection and conditional variance: Orthogonal projection of X onto functions of finite-range Y equals a function of Y representing the conditional expectation of X.The expected conditional variance follows from the orthogonality of the residual to all functions of Y.
  • Binary case: For a binary Y, the functions {1,Y} form an orthonormal basis for the subspace of functions of Y.The projection of X is expressed using the correlation parameter ρ.
  • Binary case: The binary-case identity follows from X^2 = Var X and ρ^2 = Cov(X,Y)^2 / Var Y.These substitutions connect the projection calculation to the desired variance formula.
Loading 1104.4680v1…