Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.11, p. 345 — Goemans–Williamson: E ζ⊤Lζ ≥ 0.878 max over {−1,1}ⁿ of x⊤Lx for ζ = sign(ξ), ξ ∼ N(0, Σ)

Proved
ConvexOptAlg.GoemansWilliamson.theorem_6_11

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmmax-cutp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1randomized-roundingsemidefinite-programming

Let A∈R+n×nA\in\mathbb R^{n\times n}_+A∈R+n×n​ be a symmetric matrix of non-negative weights and L=D−AL=D-AL=D−A its graph Laplacian, DDD being diagonal with entries ∑jAi,j\sum_j A_{i,j}∑j​Ai,j​. Let Σ\SigmaΣ be a solution of the SDP relaxation of MAXCUT,

Σ∈arg⁡max⁡{⟨L,X⟩:X∈S+n, Xi,i=1, i∈[n]}.\Sigma\in\arg\max\bigl\{\langle L,X\rangle : X\in\mathbb S^n_+,\ X_{i,i}=1,\ i\in[n]\bigr\}.Σ∈argmax{⟨L,X⟩:X∈S+n​, Xi,i​=1, i∈[n]}.

Let ξ∼N(0,Σ)\xi\sim\mathcal N(0,\Sigma)ξ∼N(0,Σ) and ζ=sign⁡(ξ)∈{−1,1}n\zeta=\operatorname{sign}(\xi)\in\{-1,1\}^nζ=sign(ξ)∈{−1,1}n. Then ζ⊤Lζ\zeta^\top L\zetaζ⊤Lζ is integrable and

E ζ⊤Lζ ≥ 0.878max⁡x∈{−1,1}nx⊤Lx.\mathbb E\,\zeta^\top L\zeta\ \ge\ 0.878\max_{x\in\{-1,1\}^n}x^\top Lx.Eζ⊤Lζ ≥ 0.878x∈{−1,1}nmax​x⊤Lx.

This is the Goemans–Williamson guarantee: rounding the solution of a semidefinite program by a random Gaussian hyperplane produces, in expectation, a cut within a factor 0.8780.8780.878 of the maximum cut, whereas a uniformly random cut only guarantees the factor 1/21/21/2.

Formalization Note "The solution" is any maximizer of the relaxation (IsSDPRelaxationOptimum); maximizers exist because the feasible set is nonempty and compact. N(0,Σ)\mathcal N(0,\Sigma)N(0,Σ) is Mathlib's multivariateGaussian 0 Σ, defined also for singular Σ\SigmaΣ (e.g. Σ=xx⊤\Sigma=xx^\topΣ=xx⊤). The sign is {−1,1}\{-1,1\}{−1,1}-valued with sign⁡(0)=1\operatorname{sign}(0)=1sign(0)=1. The maximum over the hypercube is a finite maximum over the 2n2^n2n sign vectors. Integrability of the bounded integrand is part of the conclusion. The constant 0.8780.8780.878 is the book's.

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_GoemansWilliamson_Defs
Formal statement
namespace ConvexOptAlg.GoemansWilliamson

open MeasureTheory ProbabilityTheory Matrix

/-- **Theorem 6.11** (Goemans–Williamson; Bubeck, arXiv:1405.4980v2, §6.6, p. 345). Let
`A ∈ ℝ₊ⁿˣⁿ` be a symmetric matrix of non-negative weights and `L = D − A` its graph Laplacian.
Let `Σ` be the solution to the SDP relaxation of MAXCUT. Let `ξ ∼ N(0, Σ)` and
`ζ = sign(ξ) ∈ {−1, 1}ⁿ`. Then `E ζ⊤Lζ ≥ 0.878 max_{x ∈ {−1,1}ⁿ} x⊤Lx`.

`Σ` is any maximizer of `⟨L, X⟩` over `X ∈ S₊ⁿ` with unit diagonal; `N(0, Σ)` is Mathlib's
`multivariateGaussian 0 Σ` (well defined for singular `Σ`). The integrand is bounded and
measurable; its integrability is asserted as part of the conclusion. -/
theorem theorem_6_11 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hsymm : A.IsSymm)
    (hnonneg : ∀ i j, 0 ≤ A i j) (Sig : Matrix (Fin n) (Fin n) ℝ)
    (hopt : IsSDPRelaxationOptimum (laplacian A) Sig) :
    Integrable (fun ξ : EuclideanSpace ℝ (Fin n) => sgnVec ξ ⬝ᵥ laplacian A *ᵥ sgnVec ξ)
        (multivariateGaussian 0 Sig) ∧
      ∫ ξ, sgnVec ξ ⬝ᵥ laplacian A *ᵥ sgnVec ξ ∂(multivariateGaussian 0 Sig) ≥
        (0.878 : ℝ) * hypercubeMax (laplacian A) := by sorry

end ConvexOptAlg.GoemansWilliamson
Source
Bubeck, arXiv:1405.4980v2, Theorem 6.11, p. 345; MAXCUT and L = D − A, p. 344
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me