Uniform sparsest cut: hardness and semidefinite gaps

The explanation

Picture six computers in two groups of three. Inside each group, every pair shares a cable. One extra cable joins the two groups. That makes 7 cables among 15 pairs of computers. Where is this network weakest? One way to answer is to split the computers into two sides. Count the cables that cross the split. Then divide by the number of pairs the split separates. Splitting the two groups apart cuts 1 cable and separates 3 × 3 = 9 pairs. Its ratio is 1/9, about 0.11. Cutting off one corner computer cuts 2 cables and separates 1 × 5 = 5 pairs. Its ratio is 2/5, which is 3.6 times worse. Checking all 62 ways to pick one side confirms that 1/9 is the lowest ratio.

This lowest ratio is called the uniform sparsest cut. "Uniform" means every pair of computers counts once in the bottom number. In general each link carries a capacity, a weight that replaces the plain count of cables. Six computers are easy to check by hand. With thousands, the number of splits explodes. So people look for fast methods that come close. A method with factor C must return a split whose ratio is at most C times the lowest one.

Good fast methods exist. Leighton and Rao built one around network flows, with guarantees that grow like the logarithm of the network size. Arora, Rao and Vazirani improved the factor to grow like the square root of that logarithm. Their work was first presented in 2004. It uses a semidefinite relaxation. That is an easier problem that places the computers as points in a high-dimensional space instead of on two sides. Its best value can be computed fast, and it is never above the true lowest ratio.

On the other side, finding the exact lowest ratio was already known to be NP-hard. That means a fast exact method would give fast methods for a huge class of hard problems, called NP. Matula and Shahrokhi showed this in 1990. Ruling out a rough answer is a different question. Earlier lower bounds of that kind leaned on unproved assumptions. One, by Raghavendra, Steurer and Tulsiani, rests on the Small-Set Expansion hypothesis.

The first paper claims to prove that, for every fixed factor C above 1, getting within factor C is NP-hardSource 1. It uses no unproved hypothesisSource 2. It turns any logic formula of a standard kind into a network and a threshold number. If the formula can be satisfied, the lowest ratio is at most the threshold. If not, every split has a ratio above C times the thresholdSource 3. The main difficulty is a split that separates very littleSource 4. Such a split must still reveal a solution to the formula. So every error has to be measured against the pairs the split separates, not against one fixed allowance. In the six-computer picture, a factor-3 method may return any split with ratio up to 1/3. The claim says no fast method can promise even that in general, unless every NP problem has a fast method.

The second paper studies the relaxation itself. Its integrality gap is the true lowest ratio divided by the relaxation's best value. A large gap means the relaxation badly underestimates some networks. Here n counts the computers. The Arora, Rao and Vazirani method caps this gap at a constant times the square root of log n. Before, the best lower bounds were much smaller. Devanur, Khot, Saket and Vishnoi showed a gap growing like log log n in 2006. Kane and Meka raised it in 2013. The second paper proves gaps of at least a constant times √log n, divided by (log log n)³Source 5. That matches the known cap up to a power of log log nSource 6.

The obstacle here was averagingSource 7. For networks where only chosen pairs count, Naor and Young had already reached the square-root size in 2018. Those examples fail only on a few pairs. They do not carry over when every pair counts equally. The new construction builds point positions that are far apart on average. It then shows that every way of squashing them into split-friendly form loses most of that average distanceSource 8.

The gap grows very slowly, and the bound carries an unknown constant. With natural logarithms and n = 10^100, the square root of log n is about 15.2. The full expression is about 0.094 before the constant. So the result says something only for astronomically large networks. It also holds along a sequence of sizes, not for every sizeSource 5. Neither paper rules out a fast method whose factor grows with n.

How sure is this? A computer proof checker called Lean has checked the second paper's main statement. It covers the gap of at least a constant times √log n over (log log n)³. The check holds along a sequence of sizes, with every pair counting once. The Lean scope note lists nothing for the first paper's hardness claim, so that claim rests on its written proof. No specialists have published a review yet.

What it doesn't show. This does not rule out a fast method whose factor grows with network size, like the square root of log n.