PaperlayerView exact revision on arXiv

Source-linked AI summary

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

David García-Soriano, Atsushi Miyauchi

arXiv:2609.35453v1cs.DS

TL;DR

The Frieze–Jerrum rounding is hard to analyze because its collision probability lacks a tractable general-k formula. The paper uses Hermite-based analysis and an edge-wise framework to bound mixtures of rounding schemes, obtaining a 0.7818 MaxAgree approximation versus Swamy’s 0.7666.

  • Problem

    For general k, the collision probability central to edge-wise analysis has no comparably tractable closed-form representation.

    Source: §1 · p. 4

  • Method

    The paper uses the Hermite representation of collision probabilities and develops an edge-wise framework certifying upper bounds for mixtures over finite rounding families.

    Source: §1.4 · p. 13, §2.4 · p. 17

  • Results

    0.7818 for MaxAgree versus Swamy’s 0.7666; the standard SDP integrality ratio is at most 0.802, and exceeding it is Unique Games-hard.

    Source: §1 · p. 5

  • Takeaways & Limitations

    For MaxAgree, the 0.7818 guarantee leaves only tiny room for improvement within the tested rounding family and edge-wise analysis framework.

    Source: §1.4 · p. 14

    The upper-bound framework applies to mixtures over a prescribed finite family of rounding schemes under edge-wise analysis.

    Source: §1.4 · p. 13

Abstract

from arXiv · show

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(\rho)$ that two nodes whose SDP vectors have inner product $\rho$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). On the hardness side, we show that the integrality ratio of the standard SDP relaxation is at most $0.802$, and that approximation beyond that is Unique Games-hard. We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$.

1 Introduction

The FJ rounding’s approximation analysis depends on a collision probability that lacks a tractable general closed form, making accurate certification difficult. The paper develops a Hermite-based certification framework and applies it to improve clustering and graph-partitioning guarantees.

1 Introduction

  • The Hermite-coefficient certification framework derives accurate, tractable bounds on FJ collision probabilities without requiring a closed-form representation.It reduces coefficient computation to one-dimensional Gaussian integrals and certifies finitely many coefficients to bound the full probability function.Source: §1 · p. 4
  • 0.7818 is the paper’s polynomial-time MaxAgree approximation, improving on Swamy’s 0.7666 ratio.The analysis uses carefully chosen mixtures of k-spokes roundings.Source: §1 · p. 5
  • The framework also improves guarantees for MaxAgree[K] and modularity maximization, and gives a tighter characterization of the Frieze–Jerrum Max K-Cut ratio.For Max K-Cut, the characterization is proved tight for the algorithm and determined to high precision for a range of K.Source: §1 · p. 5
  • 0.802 is an upper bound on the integrality ratio of the standard MaxAgree SDP, and approximation beyond it is Unique Games-hard.Under the Unique Games Conjecture, the best polynomial-time approximation ratio lies in [0.7818, 0.802].Source: §1 · p. 5
  • The paper bounds what mixtures of prescribed rounding families can certify under edge-wise analysis, finding its proposed MaxAgree and MaxAgree[K] mixtures nearly optimal within their respective families.These bounds concern the specified families and analysis framework, not all possible algorithms.Source: §1 · p. 5

1.1 Hermite-Coefficient Certification Framework

The framework expresses the collision probability through a Hermite expansion and certifies its coefficients using one-dimensional Gaussian integrals. Nonnegativity lets finitely many certified coefficients bound the full probability function, while a structural property of separation probability simplifies later analyses.

1.1 Hermite-Coefficient Certification Framework

  • The FJ collision probability is a sum of Gaussian noise stabilities of argmax regions, and its Hermite expansion has coefficients formed from sums of squares.For two SDP vectors with inner product ρ, their Gaussian inner-product vectors are ρ-correlated.Source: §1.1 · p. 5
  • Symmetry and conditioning on the winning Gaussian coordinate reduce each coefficient to a nonnegative weighted sum of squares of structured one-dimensional Gaussian integrals.The direct coefficient definition instead involves k-dimensional Gaussian integrals over argmax regions.Source: §1.1 · p. 6
  • Validated interval integration on a bounded domain and analytic Gaussian tail bounds rigorously enclose the signed integrals before they are squared.The resulting enclosures are propagated through the sum-of-squares representation to obtain certified rational coefficient bounds.Source: §1.1 · p. 6
  • Certifying finitely many coefficients suffices to bound the entire collision-probability function by using coefficient nonnegativity and the total coefficient mass.For negative correlations, alternating powers require different coefficient-bound choices by degree parity; the construction also extends by linearity to mixtures of k-spokes roundings.Source: §1.1 · p. 6
  • The normalized separation probability is nondecreasing on ρ ∈ [−1/2, 1), and this remains true for arbitrary mixtures of k-spokes roundings.This reduces certain interval-wide inequalities in approximation analyses to checking a single endpoint and helps prove the Max K-Cut conjecture.Source: §1.1 · pp. 6–7

1.2 Improved Approximations

The paper uses Hermite-coefficient certification to bound Frieze–Jerrum collision probabilities and certify improved approximation guarantees. It applies this framework to MaxAgree, MaxAgree[K], Max K-Cut, and modularity maximization.

1.2 Improved Approximations

  • The framework makes collision-probability bounds usable in edge-wise certification by reducing the required checks to finite, exactly checkable conditions.For mixtures of k-spokes roundings, the negative-edge inequality reduces to checking the endpoint a.Source: §1.2 · pp. 7–8

1.2.1 MaxAgree

  • 0.7818 versus Swamy’s 0.7666: the polynomial-time MaxAgree algorithm uses 4-spokes and 5-spokes rounding, without random-hyperplane rounding.It solves the standard SDP and returns the better of the two rounded clusterings.Source: §1.2.1 · pp. 8–9

1.2.2 MaxAgree[K]

  • For K = 3, . . . , 16, the algorithm improves the best known MaxAgree[K] ratios; for K = 3, it achieves 0.8151 versus Swamy’s 0.77.It applies k-spokes roundings for 1 ≤ k ≤ K and returns the clustering with the largest objective value.Source: §1.2.2 · p. 9

1.2.3 Max K-Cut

  • The tight approximation ratio αFJ is pinned down to within 10−6, and lower bounds improve prior explicit ratios of Frieze and Jerrum and Newman [57] for K = 4, . . . , 16.The minimum occurs at ρ = −1/(K −1), resolving affirmatively the conjecture of de Klerk, Pasechnik, and Warners.Source: §1.2.3 · p. 10

1.2.4 Modularity Maximization

  • 0.3790: the polynomial-time modularity algorithm reduces the additive approximation error from 0.42084.It uses 7-spokes rounding; under the stated analysis, no mixture in the specified rounding family certifies an error below 0.3785.Source: §1.2.4 · p. 11

1.3 Inapproximability of MaxAgree under the UGC

The paper bounds the standard MaxAgree SDP’s integrality ratio and establishes Unique Games hardness beyond that bound. Its argument combines a Gaussian gap construction with a transfer to the standard relaxation.

Results

  • The standard SDP integrality ratio is at most 0.802, and under the UGC, weighted MaxAgree is NP-hard to approximate within 0.802 + ε.Together with the 0.7818 rounding, the integrality ratio lies in [0.7818, 0.802].Source: §1.3 · p. 12

Reduction to a CSP and canonical SDP

  • The proof relates MaxAgree’s standard SDP to canonical SDPs for MaxAgree[k], whose pairwise local distributions yield the constraint kY − Jn ⪰ 0.The canonical SDPs converge to the standard SDP as k → ∞.Source: §1.3 · p. 12

Gaussian integrality gap

  • The Gaussian construction bounds integral clustering agreement using Borell’s inequality applied separately to each cell, while shifted vectors address the standard SDP’s nonnegative-inner-product constraints.The cell-wise use of the inequality is lossy; the shifted-vector instance and strong-gap transfer are needed to establish the standard SDP bound.Source: §1.3 · p. 13
  • A Gaussian-space instance gives an inverse gap close to 0.802 for a weaker relaxation, and the strong-gap theorem transfers the gap to the standard SDP.The transfer preserves the gap up to arbitrarily small additive errors, including for relaxations with consistent local distributions on bounded-size node sets.Source: §1.3 · p. 13

1.4 Limitations of Rounding Families under the Edge-Wise Analysis

The paper gives a framework for upper-bounding the guarantees achievable by mixtures of rounding schemes under edge-wise analysis. It finds that its MaxAgree and MaxAgree[K] mixtures leave little room for improvement within the studied families.

1.4 Limitations of Rounding Families under the Edge-Wise Analysis

  • The framework upper-bounds the best approximation ratio certifiable by mixtures from any prescribed finite rounding family under edge-wise analysis.It uses a finite LP relaxation with rational test points and certified collision-probability bounds; a rational dual certificate gives a rigorous upper bound.Source: §1.4 · pp. 13–14
  • For MaxAgree, the studied family cannot certify above 0.78187, close to the algorithm’s 0.7818; Swamy’s subfamily cannot exceed 0.77222.The broader family includes k-spokes for 1 ≤ k ≤ 32 and k-hyperplane roundings for 1 ≤ k ≤ 5.Source: §1.4 · p. 14
  • For each K = 3, . . . , 16, MaxAgree[K] guarantees are nearly optimal among mixtures of k-spokes roundings with 1 ≤ k ≤ K under edge-wise analysis.This is the same rounding family used by the algorithm.Source: §1.4 · p. 14

2 Hermite-Coefficient Certification Framework

The framework analyzes Frieze–Jerrum rounding through the collision probability determined by the correlation of two SDP vectors. It uses Hermite expansions and certified coefficient bounds to derive rigorous bounds on collision probabilities and structural results for separation probabilities.

2.3 Hermite Expansion of Collision Probabilities

  • The framework derives a Hermite expansion of the collision probability and reduces its coefficient computation from k-dimensional Gaussian integrals over argmax regions to one-dimensional Gaussian integrals.The coefficient representation uses symmetry and conditioning on the winning Gaussian coordinate.Source: §2 · p. 14, §2.5 · p. 18

2.2 Frieze–Jerrum Rounding and Collision Probabilities

  • The k-spokes rounding assigns each node to the Gaussian vector with the largest inner product, and a pair’s collision probability depends only on their SDP-vector inner product ρ.The method uses k independent Gaussian vectors.Source: §2.2 · p. 16

2.4 A Structural Property of Separation Probabilities

  • R_k is nondecreasing on ρ ∈ [−1/2, 1), and the structural result reduces an edge-wise negative-edge inequality to a single endpoint condition.The result also leads almost immediately to a proof of a long-standing conjecture about Frieze–Jerrum rounding for Max K-Cut.Source: §2.4 · pp. 17–18

2.5 Certified Bounds on the Power-Series Coefficients

  • Signed one-dimensional integrals are enclosed with certified intervals and explicit tail bounds, which yield rational lower and upper bounds on the Hermite coefficients.Because the integrals are signed and the coefficient formula uses their squares, truncating the tails alone does not generally certify either bound.Source: §2.5 · p. 19

2.6 Certified Bounds on Collision Probabilities

  • For ρ ∈ [0, 1], the certified coefficient bounds give an upper bound on P_k(ρ); for ρ ∈ [−1, 0], they give lower and upper bounds.The bounds use finitely many certified coefficients.Source: §2.6 · p. 20

3 Derivation of the Certified Bounds on the Power-Series Coefficients

This section develops a certified computation of Hermite coefficients by reducing their defining integrals, exploiting normalization and symmetry, and enclosing signed integrals and their tails. The resulting rational coefficient bounds can be generated and reused in application-specific computations.

3.1 Reduction to One-Dimensional Gaussian Integrals

  • Conditioning on the winning Gaussian coordinate reduces the Hermite coefficients over argmax regions to one-dimensional integrals, with the exact coefficient formula obtained from that reduction.The reduction is the basis for the later certification procedure.Source: §3 · p. 21, §3.1 · p. 22

3.2 Normalization and Grouping by Symmetry

  • For 2 ≤ k ≤ 32 and 1 ≤ m ≤ 24, symmetry grouping reduces the required integrals from about 9.93 × 10^15 to 8.10 × 10^5.Grouping the remaining coordinates by their multiset also makes the coefficient bounds assemblable using exact rational arithmetic.Source: §3.1 · p. 22, §3.2 · pp. 23–24

3.3 Rigorous Enclosures: Finite Window and Signed Tails

  • Signed integral tails may reinforce or cancel the finite-window contribution, so the procedure encloses each integral and its tail before bounding its square.Validated numerical integration encloses the finite-window integral, while an explicit analytic estimate bounds the tail.Source: §3.3 · pp. 24–25

3.4 Assembling the Certificate

  • Rational intervals for the integrals yield certified rational lower and upper bounds on each coefficient by bounding the squared terms and assembling their positive weighted contributions.The degree-zero coefficient is exact: c_k,0 = 1/k.Source: §3.4 · p. 27

3.5 Implementation in Ball Arithmetic with FLINT/Arb

  • The implementation produces reusable rational coefficient bounds using validated ball arithmetic for numerical evaluation and exact rational arithmetic for the remaining coefficient computations.The generated bounds are used in application-specific computations without repeating the numerical integration.Source: §3.5 · pp. 27–28

4 Improved Approximations

This section applies Hermite-coefficient bounds and a unified edge-wise SDP analysis to certify approximation guarantees for MaxAgree, MaxAgree[K], and Max K-Cut. It also analyzes modularity maximization, proving an expected additive error of 0.3790 and near-optimality within a specified rounding family.

4.1 General Clustering Problem, SDP Relaxations, and Edge-Wise Analysis

  • The unified framework models weighted positive and negative edges through SDP relaxations and reduces approximation guarantees to positive-edge inequalities over a correlation interval and a negative-edge inequality at its endpoint.The general edge-labeled clustering problem includes MaxAgree, MaxAgree[K], and Max K-Cut as special cases.Source: §4 · p. 29, §4.1 · pp. 30–31

4.2 Finite Certification of the Positive-Edge and Negative-Edge Inequalities

  • Finite Hermite-coefficient bounds reduce these inequalities to exact rational checks, using Bernstein certificates to verify the positive-edge condition across its full interval.Subdivision yields a finite certificate when the polynomial is strictly positive, and the verifiers use exact integer or rational arithmetic.Source: §4.2 · pp. 31–32

4.3 MaxAgree

  • 0.7818 is the expected approximation ratio proved for MaxAgree using a mixture of 4-spokes and 5-spokes roundings.The algorithm returns the better clustering from those two roundings; the negative-edge inequality is verified analytically and the positive-edge inequality with Bernstein certificates.Source: §4.3 · pp. 32–33

4.4 MaxAgree[K]

  • For MaxAgree[K] with K = 3, the algorithm achieves 0.8151 versus Swamy’s previous state-of-the-art ratio of 0.77.The algorithm applies k-spokes roundings for k = 1, . . . , K and returns the best clustering; the reported ratios for K = 3, . . . , 16 are in Table 2.Source: §4.4 · pp. 33–34, Table 2 · p. 34

4.5 Max K-Cut

  • For every K ≥3, the minimum of AK(ρ) occurs at ρ = aK, and the resulting Frieze–Jerrum ratio is tight for the K-Cut algorithm.This establishes the previously open endpoint characterization for K ≥4; it was previously known only for K = 3.Source: §4.5 · pp. 35–36
  • Within 10^-6, the certified lower and upper bounds pin down the Frieze–Jerrum Max K-Cut ratio for every K = 3–16.The lower bounds improve previous state-of-the-art explicit approximation ratios for K = 4–16.Source: Table 3 · p. 37, §4.5 · p. 37
  • For K = 6 and 10, prior numerical Max K-Cut estimates exceed the paper’s rigorous upper bounds and therefore are not certified lower bounds.The cited numerical estimates are based on numerical integration and are not necessarily rigorous.Source: §4.5 · p. 37

4.6 Modularity Maximization

  • 0.3790 is Algorithm 5’s expected additive approximation error for modularity maximization.The analysis is not edge-wise; it uses a k-spokes rounding counterpart of a prior lemma.Source: §4.6 · pp. 38–40
  • 0.3785 is a lower bound on the additive error certifiable by mixtures of k-spokes roundings for 1 ≤ k ≤ 32 and k-hyperplane roundings for k ≥ 1 under the same analysis.Thus Algorithm 5 is nearly optimal within that family when the analysis uses Lemma 4.13 followed only by q < 1.Source: §4.6 · pp. 40–41

5 Inapproximability of MaxAgree under the UGC

This section establishes a 0.802 upper bound on the standard MaxAgree SDP’s integrality ratio and UGC-hardness for approximating weighted MaxAgree beyond that bound. It develops the result using Gaussian fractional solutions and a quadratic upper bound on noise stability.

5 Inapproximability of MaxAgree under the UGC

  • The standard MaxAgree SDP has integrality ratio at most 0.802, and achieving a factor above 0.802 + ε is Unique Games-hard for every ε > 0.More generally, the hardness threshold is αSDP + ε, where αSDP is the standard SDP’s integrality ratio.Source: §5 · p. 41

5.1 Reduction to a Fixed Number of Clusters

  • Restricting MaxAgree to k clusters loses at most a factor 1 − 1/k, and clusters can be assigned to buckets deterministically.Randomly hashing clusters preserves satisfied positive edges and retains each satisfied negative edge with probability 1 − 1/k.Source: §5.1 · pp. 41–42

5.2 The Canonical SDP for MaxAgree[k]

  • For instance I, SDPk(I) is the optimum of SDP(−1/(k − 1)) on I; the cited comparison gives Y′ value at least (1 − 1/k) times the value of Y.Source: §5.2 · p. 44

5.3 UGC-Based Inapproximability

  • A gap point (c, s) for the constraint-pair relaxation rules out unrestricted MaxAgree approximation ratios strictly greater than s/[c(1 − 1/k)] under the UGC.The proof transfers hardness from fixed-k instances to unrestricted MaxAgree using the 1 − 1/k reduction bound.Source: §5.3 · p. 45

5.4 A Gaussian Construction with Integrality Ratio at Most 0.802

  • The Gaussian construction contrasts equality constraints on 3/4-correlated pairs with inequality constraints on independent pairs, making their partition requirements incompatible.The sampler uses probabilities 4/7 and 3/7, respectively.Source: §5.4 · p. 46

5.4.1 Borell’s inequality and a partition-independent bound

  • With ρ = α = 3/4 and weights 4/7 and 3/7, the construction gives a numerical inverse-gap bound of about 0.80192.The corresponding β* is approximately 0.452895, attained near p = 0.195.Source: §5.4.1 · p. 47

5.4.2 The fractional solution and the resulting gap

  • The fractional solution’s value tends to 6/7 as k grows, using a shifted, hashed kernel to meet SDP constraints that the directional kernel violates.For fixed k, pairs violating the kernel’s nonnegativity condition have vanishing total weight as dimension grows; deleting them yields auxiliary CSPs that can be discretized.Source: §5.4.2 · p. 48
  • A simplex-based label-symmetric construction gives retained pairs feasible local distributions with uniform marginals and same-label probability yk(x, y).Discretization yields finite instances whose total weight and fractional objective approach those of the retained continuum instance.Source: §5.4.2 · pp. 49–50
  • For every fixed k ≥ 2, requiring local distributions on all node pairs does not change the integrality gap.The strong-gap transfer uses the Raghavendra–Steurer theorem to obtain instances with local label distributions on every pair.Source: §5.4.2 · p. 50
  • The standard SDP’s integrality ratio is at most 401/500 = 0.802, yielding 0.802 + ε inapproximability under UGC.The proof also derives the limiting ratio 500/401 from the Gaussian integrality-gap construction.Source: §5.4.2 · pp. 50–51

5.4.3 A quadratic bound on noise stability

  • The quadratic bound H(p) = 4Λ3/4(p) − 3p^2 − (453/250)p ≤ 0 holds on [0, 1].The proof bounds the tangent at p0 = Φ(−56/65) at both endpoints and certifies the inequalities using exact rational interval arithmetic.Source: §5.4.3 · p. 51

6 Limitations of Rounding Families under the Edge-Wise Analysis

This section bounds what finite families of rounding schemes can certify under edge-wise analysis, using LP duality and certified collision-probability bounds. The results show that the paper’s MaxAgree and MaxAgree[K] algorithms are nearly optimal within their respective tested families and this analysis framework.

6 Limitations of Rounding Families under the Edge-Wise Analysis

  • The upper bounds show that the algorithms for MaxAgree and MaxAgree[K] are nearly optimal within their specified rounding families and edge-wise analysis.The section develops a general certification framework for mixtures over finite rounding families.Source: §6 · p. 52

6.1 An Upper-Bound Certification Framework

  • The framework formulates the best certifiable mixture ratio as a semi-infinite LP and relaxes it using rational test points and certified collision-probability bounds.A rational feasible dual solution gives an upper bound by weak duality.Source: §6 · p. 52, §6.1 · pp. 53–54

6.2 Implementation and Certificates

  • The certificate checker verifies rationalized dual variables and all dual inequalities using exact rational arithmetic.Floating-point optimization only finds a candidate dual solution; it is not part of verification.Source: §6.2 · p. 55

6.3 Applications to MaxAgree and MaxAgree[K]

  • The 0.7818 MaxAgree mixture is nearly optimal within the tested family, whose certified upper bound is 0.78187.Within Swamy’s subfamily, no mixture certifies more than 0.77222, so reaching 0.7818 requires moving beyond that subfamily.Source: §6.3 · p. 55
  • For each K from 3 through 16, no mixture of k-spokes roundings for 1 ≤ k ≤ K certifies a ratio above the corresponding Ucert in Table 2.For these families, the negative-edge constraint is tested at a single point.Source: §6.3 · p. 55

7 Related Work

The related work situates the paper’s Hermite analysis among Gaussian-rounding methods and computer-assisted searches over rounding mixtures. It also connects the results to prior work on Max K-Cut, Gaussian partitions, correlation clustering, and modularity maximization.

Hermite expansions and Gaussian rounding

  • The Hermite representation yields nonnegative power-series coefficients for Pk, reduces their computation to one-dimensional integrals at every degree, and provides the monotonicity used to prove a Max K-Cut conjecture.Frieze and Jerrum [30] established the expansion and reduced the first few coefficients; this work gives the reduction in closed form for all degrees.Source: §7 · p. 56
  • Unlike Heilman’s [41] work on planar threshold functions for Grothendieck’s inequality, this paper analyzes k-way argmax partitions across k and the full correlation range.Coordinate symmetries reduce about 10^16 coefficients to about 10^6 integrals for k ≤ 32 and degrees up to 24.Source: §7 · p. 56

Computer-assisted analysis and rounding mixtures

  • Computer-assisted searches have also improved longstanding guarantees through optimized mixtures, including results for Max 2-AND, Max Di-Cut, and Multiway Cut.The cited Multiway Cut work improves 1.2965 to 1.2787 using mixtures of hundreds of rounding schemes.Source: §7 · p. 56

Max K-Cut

  • For Max K-Cut, the paper sharpens analysis of the original Frieze–Jerrum scheme, while Newman [57] provides an alternative scheme with an explicit collision probability for general K.Shinde, Narayanan, and Saunderson [69] pursue a complementary goal of reducing memory use while retaining guarantees close to SDP roundings.Source: §7 · p. 56

Gaussian partitions and inapproximability

  • The MaxAgree integrality-gap construction applies Borell’s inequality separately to each Gaussian partition cell, and its UGC connection uses the CSP framework and strong-gap results.For Max K-Cut, the endpoint characterization connects the standard simplex conjecture at ρ = −1/(K − 1) to matching UGC-hardness via the reduction of Isaksson and Mossel.Source: §7 · p. 57

Correlation Clustering; Modularity Maximization

  • Prior MaxAgree and MaxAgree[K] PTAS results concern unweighted complete graphs, while this paper’s modularity result continues work using the same SDP relaxation and Frieze–Jerrum rounding.Kawase, Matsui, and Miyauchi analyzed additive error directly; dense graphs also admit additive approximation schemes.Source: §7 · p. 57

AI Methodologies Statement

The authors report using AI assistance for implementation and verification code, while retaining responsibility for the paper’s contents.

AI Methodologies Statement

  • The authors used ChatGPT (GPT-5.6 Sol) to assist with portions of implementation and verification code, then independently reviewed, tested, and validated the code.They state that they take full responsibility for the paper’s contents.Source: AI Methodologies Statement · p. 57
Loading 2609.35453v1…