OctoInformBeta

Uniform sparsest cut: near-square-root semidefinite gaps

A sparsest cut on a finite vertex set with nonnegative pair capacities and nonnegative pair demands is a partition into two nonempty parts minimizing the crossing capacity divided by the separated demand. Uniform sparsest cut is the special case in which every pair of distinct vertices has demand one. For an integer n≥2n \ge 2 and vertex set [n]={1,…,n}[n] = \{1, \ldots, n\}, let C=(cij)C = (c_{ij}) assign arbitrary symmetric nonnegative capacities to unordered pairs of distinct vertices. The uniform sparsest-cut optimum is OPT⁡(C)=min⁡⌀≠B⊊[n]∑i∈B,j∉Bcij|B|(n−|B|)\operatorname{OPT}(C) = \min_{\varnothing \ne B \subsetneq [n]} \frac{\sum_{i \in B,\, j \notin B} c_{ij}}{|B|(n - |B|)}. A negative-type semimetric on a finite set VV is a function d:V×V→[0,∞)d : V \times V \to [0, \infty) satisfying all triangle inequalities for which there exist vectors xux_u (u∈Vu \in V) in a real Hilbert space with d(u,v)=∥xu−xv∥2d(u,v) = \|x_u - x_v\|^2 for all u,v∈Vu, v \in V, permitting zero distance between distinct points. The Goemans-Linial relaxation is GL⁡(C)=min⁡{∑1≤i<j≤ncijd(i,j):∑1≤i<j≤nd(i,j)=1,d is a negative-type semimetric on [n]}\operatorname{GL}(C) = \min\left\{\sum_{1 \le i < j \le n} c_{ij} d(i,j) : \sum_{1 \le i < j \le n} d(i,j) = 1,\ d \text{ is a negative-type semimetric on } [n]\right\}. When GL⁡(C)>0\operatorname{GL}(C) > 0, the integrality gap of CC is OPT⁡(C)/GL⁡(C)\operatorname{OPT}(C)/\operatorname{GL}(C). The central question is how large this integrality gap can be as a function of nn.

Linial, London, and Rabinovich established the metric correspondence between cuts and finite ℓ1\ell_1 embeddings. Rabinovich (2003) and Rabinovich (2008) developed the average-distortion framework connecting uniform sparsest cut to the average distance preserved by maps into ℓ1\ell_1 that do not increase pairwise distances. For uniform sparsest cut, Arora, Rao, and Vazirani gave an O(log⁡n)O(\sqrt{\log n}) approximation. Devanur, Khot, Saket, and Vishnoi proved an Ω(log⁡log⁡n)\Omega(\log\log n) integrality gap for uniform sparsest cut. Kane and Meka subsequently improved this integrality-gap bound to exp⁡(Ω(log⁡log⁡n))\exp(\Omega(\sqrt{\log\log n})). For arbitrary demands, the Goemans-Linial conjecture predicted a constant integrality gap. Khot and Vishnoi disproved this conjecture. Lee and Naor, Cheeger and Kleiner, Cheeger, Kleiner, and Naor (2009), and Cheeger, Kleiner, and Naor (2011) developed a geometric line of work. Naor and Young obtained the sharp Ω(log⁡n)\Omega(\sqrt{\log n}) general-demand lower bound. Chang, Naor, and Ren proved the matching upper bound.

The preprint proves that there exist an absolute constant c>0c > 0 and uniform sparsest-cut capacity instances C(j)C^{(j)} on nj→∞n_j \to \infty vertices with GL⁡(C(j))>0\operatorname{GL}(C^{(j)}) > 0 such that OPT⁡(C(j))/GL⁡(C(j))≥clog⁡nj/(log⁡log⁡nj)3\operatorname{OPT}(C^{(j)}) / \operatorname{GL}(C^{(j)}) \ge c \sqrt{\log n_j} / (\log\log n_j)^3 for all sufficiently large jj.

The Lean library SparsestCut formalizes this uniform sparsest-cut integrality-gap bound and its supporting results. OpenAI catalog entry 117 also lists a companion preprint on constant-factor hardness of uniform sparsest cut, which is not covered here, as the Lean library formalizes only the results of the preprint on uniform sparsest-cut integrality gaps. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference. Where the preprint states a result differently, the statement on the page is the Lean library’s, with the preprint’s given beside it. The preprint is a guide only, giving the results their order and their names.

The Lean library: SparsestCut

SparsestCut is a Lean library: 16 items, in six groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. Uniform sparsest cut and the Goemans-Linial relaxation Uniform sparsest cut and the Goemans-Linial relaxation.
  2. Theorem 1.1 Uniform sparsest cut has an unbounded Goemans-Linial integrality gap.
§2. Families of directions 2 items
  1. Direction families and chart maps Chart maps of pivoted direction families have left pseudoinverses.
  2. Lemma 2.1 Existence of direction families for sufficiently large dimension.
§3. A Hilbert kernel with chart extensions 4 items
  1. The common kernel and rounded chart labels A Hilbert kernel with chart extensions and rounded vertices.
  2. Lemma 3.1 Approximating Euclidean distance with a truncated Hilbert kernel.
  3. Lemma 3.2 Chart extension bounds and Hilbert kernel segment estimates.
  4. Lemma 3.3 Angle and Hilbert kernel bounds with chart rounding.
§4. The finite negative-type semimetric 3 items
  1. Negative-type semimetrics and chart repair Chart triangle repair definitions and source metric parameters.
  2. Lemma 4.1 Repairing triangle deficits into a negative-type semimetric.
  3. Proposition 4.2 Large direction families induce finite negative-type semimetrics.
§5. Contractions into ℓ₁ 3 items
  1. Smoothing, interface jumps, and gradient budgets Mollified chart step functions satisfy error and gradient bounds.
  2. Proposition 5.1 Average ℓ1\ell_1 displacement bound for chart cell functions.
  3. Lemma 5.2 Cube and Gaussian measures satisfy first-moment Poincaré inequalities.
§6. Exactly uniform demands 2 items
  1. Multiplicities and vertex replication Vertex replication transfers metric and contraction bounds.
  2. Lemma 6.1 Cut-cone duality gives capacities with sparsity at least one.

No item matches.