Uniform sparsest cut: hardness and semidefinite gaps

Source and verification

This article explains family 117 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Cuts, capacities, and uniform demand

Let $G$ have $n\ge 2$ vertices and nonnegative capacities $c_{ij}=c_{ji}$ on distinct pairs. A cut is a nonempty proper set $S$ of vertices. Its crossing capacity is the sum of $c_{ij}$ over pairs with one endpoint in $S$ and the other outside it, counted once. Its uniform sparsity is

$${\Phi }_G(S)=\frac{{\sum }_{i\in S,j\notin S}{c}_{ij}}{|S|(n-|S|)}.$$

Write $\Phi (G)={\min }_S{\Phi }_G(S)$. The denominator counts separated vertex pairs: every distinct pair carries demand one, independently of the supply capacities. This differs from normalizing by vertex degrees, and from allowing an arbitrary selected set of demand pairs.

For example, join two disjoint cliques of size $r$ by one edge of capacity $ϵ$, with all clique edges of capacity one. The cut between the cliques has sparsity $ϵ/r^2$. A cut isolating a nonbridge vertex has sparsity $(r-1)/(2r-1)$. The denominator rewards a bottleneck separating many pairs, while still requiring the optimization to consider singletons and other small cuts.

A factor-$C$ approximation returns an actual cut of value at most $C\Phi (G)$. An integrality gap instead compares this optimum with the value of a specified relaxation. The two manuscripts address these different questions.

🏷️ Two family statements

Hardness manuscript

For every fixed real $C>1$, the manuscript gives a polynomial-time reduction from 3CNF satisfiability to a graph with nonnegative rational capacities and a positive rational threshold $a$, such that

$$\begin{array}{rl}\text{YES}& ⟹\Phi (G)\le a,\\ \text{NO}& ⟹\Phi (G)>Ca.\end{array}$$

YES denotes satisfiable formulas and NO denotes unsatisfiable formulas. All demands are exactly one. Graph size and numerical bit lengths are polynomial in the formula size, with exponents allowed to depend on the fixed $C$. (OpenAI, 2026)

This is an ordinary NP-hardness claim, rather than one conditional on a conjecture about small-set expansion. Its algorithmic consequence remains conditional on $P\ne NP$: the reduction itself does not prove that separation. It also does not give a running-time exponent uniform in a variable approximation factor.

For the second statement, a negative-type semimetric has the form $d(i,j)=\Vert x_i-x_j{\Vert }_2^2$ and satisfies the triangle inequalities. Distinct vertices may have distance zero. Squared Euclidean distances alone need not satisfy triangles, so that requirement is additional. Define

$$\begin{array}{c}\mathrm{GL}(G)=\underset{d}{\min }\sum _{i<j}{c}_{ij}d(i,j),\\ \sum _{i<j}d(i,j)=1,\end{array}$$

where the minimum is over these semimetrics. No unit-norm constraint is imposed on the vectors. A cut distance $|1_S(i)-1_S(j)|$, divided by $|S|(n-|S|)$, is feasible. Thus $\mathrm{GL}(G)\le \Phi (G)$.

Integrality-gap manuscript

Along a sequence $n_j\to \infty$, there are nonnegative real capacity instances with positive relaxation value and

$$\frac{\Phi (G_j)}{\mathrm{GL}(G_j)}\ge c\frac{\sqrt{\log n_j}}{(\log \log n_j{)}^3}$$

for one absolute $c>0$ and all sufficiently large $j$. Every distinct pair has unit demand. (OpenAI, 2026b)

The latter statement concerns the basic Goemans–Linial SDP, an existential sequence of sizes, and real capacities. It is not by itself a polynomially encoded hardness reduction or a lower bound for every possible algorithm.

🏷️ Why small cuts require relative error

In the hardness construction, a cut becomes a Boolean response $h$ to a sampled object. If its positive mass is $p$, then

$$\begin{array}{rl}\mathrm{Var}(h)& =p(1-p)\\ & =\frac{1}{2}\mathbb{E}|h(B)-h(B^{\prime })|.\end{array}$$

where $B,B^{\prime }$ are independent. This is the probabilistic version of separated demand. An additive error $\delta$ in a comparison is useless when $p\ll \delta$: it can exceed the entire quantity being controlled. The source therefore arranges errors proportional to $p(1-p)$.

The reduction first constructs bounded-query tests of a proof-bit assignment. The finite-field and evaluation constructions are specialized testing interfaces here; their algebraic development is outside this series’ scope. What matters for the reduction is their controlled query distributions and their soundness: sufficiently consistent answers decode a satisfying assignment.

A predicate is an actual Boolean function of all proof bits, not its sampled description. A proposed valuation assigns one bit to each predicate, approximately respects inclusion between predicates, and has prescribed averages under several sampling laws. Those conditions force decoding. Treating two descriptions of the same function as independent objects would invalidate that interface.

The next argument extracts such a valuation from a rare successful conjunction. Conditioning on success and revealing a common prefix gives a density with nearly extremal entropy. Comparisons with the constant-one predicate control its upper tail. Clipping forces the density near zero and one positive level, so a common threshold yields the required valuation. Its estimates do not depend on a smallest probability atom.

Finally, a cut acts on real-valued scores assembled from rare predicates and independent amplitudes at several scales. Small resampling cost forces some amplitude to retain information about the cut. Smoothed comparison paths convert that information into the rare conjunction response. This is where error proportional to cut variance must survive every passage. (OpenAI, 2026a)

🏷️ From sampled masses to actual vertex counts

The hardness manuscript rounds scores to finite truth tables. A key records the table and its ordered essential bit names, identifying descriptions of the same function. Rational lower bounds on retained masses and upper bounds on comparison costs permit a finite graph construction.

Replicating a key according to its mass makes the probabilistic denominator into a cardinality denominator. Heavy edges discourage separating copies of one key. The remaining keys require additional edges that pay for their possible contribution to separated demand. Without that last accounting, a small cut supported on discarded or low-mass objects could defeat the soundness estimate.

The resulting claim is exactly about all nonempty proper vertex subsets and $|S|(n-|S|)$, rather than only balanced cuts under an auxiliary distribution.

🏷️ Average distortion and the SDP obstruction

An ${\ell }_1$ distance on a finite set is a nonnegative combination of cut distances. To see the basic mechanism, a real coordinate satisfies

$$|u-v|={\int }_{\mathbb{R}}|1_{u>t}-1_{v>t}|dt.$$

Summing over coordinates expresses the whole distance as weighted cuts. The companion constructs a negative-type semimetric with large average distance, but for which every contraction $F$ into ${\ell }_1$ has much smaller average distance. A contraction satisfies $\Vert F(i)-F(j){\Vert }_1\le d(i,j)$ on every pair.

Suppose the two ordered-pair averages are at least $a$ and at most $b$, respectively. Consider nonnegative cut weights $t_S$ whose combined distance is bounded by $d$. Maximizing

$$\sum _S|S|(n-|S|)t_S$$

over these weights gives an optimum at most $n^{2}b/2$. Its linear-programming dual minimizes ${\sum }_{i<j}{c}_{ij}d(i,j)$ under the constraints

$$\sum _{i\in S,j\notin S}{c}_{ij}\ge |S|(n-|S|)$$

for every cut. Hence dual capacities have $\Phi (G)\ge 1$. Dividing $d$ by its unordered-pair sum, at least $n^{2}a/2$, gives $\mathrm{GL}(G)\le b/a$.

The positive-capacity graph is connected, since otherwise a component cut violates a dual constraint. If $\gamma >0$ is the least capacity in a positive spanning tree, triangle inequalities along tree paths show that every normalized feasible distance has objective at least $\gamma /\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Thus the relaxation value is positive, including when the constructed semimetric has coincident points. This proves the finite duality step explicitly. (OpenAI, 2026b)

🏷️ The geometric construction and its logarithms

The difficult metric construction uses many rounded linear charts of one parameter cube of dimension $m$. Hilbert-space feature maps produce large global distances. Small local components control jumps at chart boundaries. A Gaussian-kernel repair enforces the triangle inequalities while retaining those small interface costs; merely bounding a global perturbation would overwhelm the tiny local distances.

All charts constrain the same contraction. After smoothing, each chart represents scalar gradients using its normals. A direction-selection estimate says that many charts have small projections in each relevant direction. Averaging across charts before summing target coordinates avoids a dependence on the target dimension. A first-moment inequality then converts gradient control into average-distance control.

The source obtains average original distance of order $m$ and average contracted distance at most $C\sqrt{m}(\log m{)}^{5/2}$. The averaging distribution is supported on one chart, but the other charts impose essential constraints. To make demand uniform, each vertex receives at least one copy, even if its original probability is zero. Copies of a vertex have distance zero, forcing any contraction to agree on them. Multiplicity rounding changes product averages by only $O(1/m)$.

The final size satisfies $\log n\asymp m\log m$. Consequently

$$\frac{\sqrt{m}}{(\log m{)}^{5/2}}\asymp \frac{\sqrt{\log n}}{(\log \log n{)}^3}.$$

The extra half-power in the denominator comes from converting $m$ to $\log n$. The construction and the separate hardness reduction are not interchangeable proofs of the same claim.

🏷️ Key steps and proof outlines

Why the cut denominator must survive decoding

For an indicator $f=1_S$ under a probability law $\mu$, let $p=\mu (S)$. Then ${\mathrm{Var}}_{\mu }(f)=p(1-p)$ and two independent samples disagree with probability $2p(1-p)$. A comparison test whose rejection probability is bounded below by a fixed multiple of this variance therefore controls a normalized cut even when $p$ is extremely small.

An additive error $\eta$ independent of $p$ would be useless once $p(1-p)\ll \eta$. The hardness manuscript’s rare-predicate and score arguments are designed to preserve the variance scale throughout smoothing and decoding. Its local extraction has to recover compatible source answers from relative information about a rare event, rather than merely detecting that the cut is nonconstant. The density-clipping argument provides a nearly two-level density on which one common threshold can encode those answers. (OpenAI, 2026a)

The final finite graph makes this normalization literal. Replication turns probabilistic mass into the number of vertices; heavy internal edges prevent a cheap cut from splitting copies representing one truth-table key. The remaining exceptional keys receive enough capacity to pay for the demand they could separate. This last charge is necessary because sparsest cut optimizes over every nonempty subset, including subsets made mostly of exceptional objects.

Turning weighted average distortion into uniform demand

The integrality-gap companion initially controls pair averages under a distribution $w$ supported on one chart. Other chart vertices have zero weight but constrain the same contraction, so they cannot simply be removed. Its section “Replacing the parameter distribution by multiplicities” gives every vertex at least one copy. For a large integer $M$, set

$$k_v=1+\lfloor M{w}_v\rfloor ,n=\sum _v{k}_v,{\mu }_v=k_v/n.$$

Write $e_v=k_v-M{w}_v\in (0,1]$ and $E={\sum }_v{e}_v$. Then $n=M+E$ and ${\mu }_v-w_v=(e_v-E{w}_v)/n$. Consequently

$$\Vert \mu -w{\Vert }_{\mathrm{TV}}\le |V|/M.$$

The source chooses $M=m^m+m^2|V|$, which makes this at most $m^{-2}$. Together with $|V|\le \exp (Cm\log m)$, this specific choice gives both bounds in $\log n\asymp m\log m$: the $m^m$ term supplies the lower bound, while the chart-size estimate supplies the upper bound. For product laws, expanding their difference gives total variation at most $2m^{-2}$. Distances are bounded by $Cm$, so their pair averages change by at most $2C/m$. This is negligible compared with the original order-$m$ distance scale. (OpenAI, 2026b)

Copies of the same vertex have distance zero. Every contraction into ${\ell }_1$ must therefore identify them. Since every original vertex has at least one copy, any contraction of the replicated space induces one on the full original space and retains all chart constraints. This proves that multiplicity rounding preserves the contraction obstruction, not only the source-distance average.

A finite dual program manufactures capacities

For each cut $S$, let ${\delta }_S(i,j)$ indicate whether it separates $i,j$. Nonnegative combinations ${\sum }_S{t}_S{\delta }_S$ are ${\ell }_1$ distances. Maximize their total unordered-pair distance subject to being bounded by the constructed semimetric $d$. The contraction theorem bounds this objective by $n^{2}b/2$.

The dual variables are capacities $c_{ij}\ge 0$. Its constraint for a cut is exactly ${\sum }_{i\in S,j\notin S}{c}_{ij}\ge |S|(n-|S|)$, so every cut has sparsity at least one. The dual objective is at most $n^{2}b/2$. Meanwhile ${\sum }_{i<j}d(i,j)\ge n^{2}a/2$, and normalizing the squared Hilbert distances by that sum produces a feasible SDP solution of value at most $b/a$.

The factor two appears in both ordered-to-unordered conversions and cancels. Keeping it in both places prevents a normalization error. Finally the size relation $\log n\asymp m\log m$ converts $\sqrt{m}/(\log m{)}^{5/2}$ into the stated near-square-root-logarithmic gap; the extra half-power of $\log \log n$ comes from the square root of the size conversion.

See Also

• Approximation gaps introduces promise reductions and the difference between a gap theorem and a complexity-class separation.
• Edit-distance embeddings studies a metric obstruction to one common embedding; here the obstruction must control the average under uniform pair demand.

🏷️ Manuscripts and verification scope

• Constant-factor hardness of uniform sparsest cut — pinned manuscript and companion source.
• Near-square-root logarithmic integrality gaps for uniform sparsest cut — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The documented comparator selects the existential sequence of uniform-demand SDP gaps. It does not select the separate computational-hardness theorem. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Constant-factor hardness of uniform sparsest cut.

🐻  OpenAI 2026b. Near-square-root logarithmic integrality gaps for uniform sparsest cut.