Krivine diffusions attain the Goemans--Williamson approximation ratio

Assaf Naor; Ronen Eldan

arxiv: 1906.10615 · v1 · pith:IXUPKHWKnew · submitted 2019-06-25 · 💻 cs.DS

Krivine diffusions attain the Goemans--Williamson approximation ratio

Ronen Eldan , Assaf Naor This is my paper

Pith reviewed 2026-05-25 15:51 UTC · model grok-4.3

classification 💻 cs.DS

keywords MAXCUTapproximation algorithmsGoemans-WilliamsonKrivine diffusionssticky Brownian motionsemidefinite programmingrounding schemes

0 comments

The pith

A slowed-down sticky Brownian motion rounds MAXCUT SDP solutions to the Goemans-Williamson approximation ratio.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors prove that a particular slowed-down version of sticky Brownian motion exists and, when applied as a rounding procedure to the vectors from the MAXCUT semidefinite program, produces cuts whose expected value meets the Goemans-Williamson guarantee of roughly 0.878 times the optimum. This directly answers a 2018 question on whether diffusion-based roundings can reach that bound. The construction is presented as one concrete instance inside the larger Krivine diffusions framework. A reader who accepts the result sees that the Goemans-Williamson performance can be realized through a continuous stochastic process rather than the original hyperplane method.

Core claim

We prove the existence of a slowed-down sticky Brownian motion whose induced rounding for MAXCUT attains the Goemans--Williamson approximation ratio. This is an especially simple particular case of the general rounding framework of Krivine diffusions.

What carries the argument

The slowed-down sticky Brownian motion, which serves as the rounding map that converts SDP solution vectors into MAXCUT partitions while preserving the Goemans-Williamson ratio.

If this is right

The Goemans-Williamson ratio for MAXCUT can be realized by a continuous-time stochastic process.
Krivine diffusions supply at least one rounding scheme that matches the best known approximation factor for this problem.
The same diffusion can be viewed as a probabilistic reinterpretation of the original hyperplane rounding.
Existence of this process supplies a concrete object whose properties can be studied independently of the MAXCUT application.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar slowed-down diffusions might be constructible for other SDP-based approximation problems whose optimal ratios are still unknown.
The approach may give a way to interpolate between different rounding schemes by varying the speed parameter of the Brownian motion.
If the general Krivine framework can be made explicit, it could yield new rounding algorithms for problems beyond MAXCUT.

Load-bearing premise

That a slowed-down sticky Brownian motion can be defined so its rounding map on SDP vectors recovers exactly the Goemans-Williamson ratio, using properties of the Krivine diffusions framework studied elsewhere.

What would settle it

An explicit MAXCUT instance together with an SDP solution vector on which the slowed-down sticky Brownian motion rounding produces an expected cut value strictly below the Goemans-Williamson fraction of the SDP value.

read the original abstract

Answering a question of Abbasi-Zadeh, Bansal, Guruganesh, Nikolov, Schwartz and Singh (2018), we prove the existence of a slowed-down sticky Brownian motion whose induced rounding for MAXCUT attains the Goemans--Williamson approximation ratio. This is an especially simple particular case of the general rounding framework of Krivine diffusions that we investigate elsewhere.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the 2018 open question by proving existence of a slowed-down sticky Brownian motion that attains the Goemans-Williamson ratio, but the argument rests on the general Krivine framework from their companion work.

read the letter

The main thing here is that Eldan and Naor have found a slowed-down sticky Brownian motion that rounds SDP solutions for MAXCUT to achieve the Goemans-Williamson ratio. This directly settles the question left open by Abbasi-Zadeh et al. in 2018. What stands out is the concrete existence result for this particular diffusion process. It fits into their broader Krivine diffusions framework, which they say they explore in a separate paper. The approach gives a stochastic process view of the rounding, which might help think about other problems in a similar way. The paper does a good job of keeping the claim focused on existence for this simple case. It avoids overclaiming and sticks to answering the specific question. On the downside, the argument appears to lean heavily on properties established in the companion work on the general framework. The abstract does not spell out how the slowdown and stickiness parameters are chosen to hit exactly the arccos(ρ)/π probability. Without seeing the full derivation or the other paper, it's hard to judge if the transfer is straightforward or if there are hidden choices. The stress-test note about implicit transfer seems to hold based on what's described. That said, since they call it an especially simple particular case, the core idea might be clean once the framework is accepted. This paper is mainly for researchers in approximation algorithms who are interested in probabilistic rounding methods and connections to stochastic processes. It could be useful for someone looking to extend these ideas to other problems. I would send it to peer review. The result is targeted and answers a clear open question, even if the details sit partly elsewhere. A referee could check the connection to the general case and see if the existence is fully rigorous here.

Referee Report

1 major / 0 minor

Summary. The manuscript proves the existence of a slowed-down sticky Brownian motion (a special case of Krivine diffusion) whose induced rounding for MAXCUT attains the Goemans-Williamson approximation ratio. The result is presented as an especially simple particular case of the general rounding framework of Krivine diffusions investigated elsewhere.

Significance. If correct, the result answers an open question of Abbasi-Zadeh et al. (2018) by exhibiting a concrete diffusion within the Krivine framework that matches the GW ratio exactly. It underscores the expressive power of the general framework for achieving optimal approximation guarantees on MAXCUT without introducing free parameters.

major comments (1)

The load-bearing step is the claim that the specific slowed-down sticky Brownian motion induces the GW rounding function arccos(ρ)/π. The manuscript states this follows immediately from the general framework but provides neither the explicit parameter values for slowdown and stickiness nor the verification that these parameters reproduce the required cut probability; the proof is therefore not self-contained.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater self-containment in the argument. We address the single major comment below.

read point-by-point responses

Referee: The load-bearing step is the claim that the specific slowed-down sticky Brownian motion induces the GW rounding function arccos(ρ)/π. The manuscript states this follows immediately from the general framework but provides neither the explicit parameter values for slowdown and stickiness nor the verification that these parameters reproduce the required cut probability; the proof is therefore not self-contained.

Authors: We agree that the manuscript as written relies on the general Krivine framework without spelling out the concrete slowdown and stickiness parameters or verifying the induced cut probability directly. This does reduce self-containment for readers who have not yet consulted the companion paper. In the revised version we will insert the explicit parameter values together with a short, direct calculation confirming that the resulting rounding function is exactly arccos(ρ)/π. revision: yes

Circularity Check

1 steps flagged

Central existence claim justified only by self-citation to general Krivine diffusions framework

specific steps

self citation load bearing [Abstract]
"This is an especially simple particular case of the general rounding framework of Krivine diffusions that we investigate elsewhere."

The manuscript states this is a simple particular case of the general rounding framework investigated elsewhere, without reproducing the required parameter selection or the derivation that the resulting cut probability equals arccos(ρ)/π for SDP inner product ρ. The load-bearing step is the implicit transfer of the general framework's guarantees to this specific diffusion.

full rationale

The paper claims to prove existence of a slowed-down sticky Brownian motion attaining the Goemans-Williamson ratio but explicitly states this is a particular case of the general framework investigated elsewhere by the same authors. The derivation chain therefore reduces to transfer of guarantees from that self-citation without reproducing parameter selection or the cut-probability derivation in this manuscript. This matches the self-citation load-bearing pattern as the central premise depends on the overlapping-authors reference.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on the existence and rounding properties of the slowed-down sticky Brownian motion within the Krivine diffusions framework. No explicit free parameters, invented entities, or additional axioms are stated.

axioms (1)

domain assumption The Krivine diffusions framework induces valid roundings for the MAXCUT SDP solution that can attain the Goemans-Williamson ratio when specialized to a slowed-down sticky Brownian motion.
Invoked implicitly by presenting the result as a particular case of the general framework.

pith-pipeline@v0.9.0 · 5580 in / 1366 out tokens · 33054 ms · 2026-05-25T15:51:49.481096+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

P. Austrin. Towards sharp inapproximability for any 2- CSP . SIAM J. Comput., 39(6):2430--2463, 2010

work page 2010
[2]

Abbasi-Zadeh, N

S. Abbasi-Zadeh, N. Bansal, G. Guruganesh, A. Nikolov, R. Schwartz, and M. Singh. Sticky brownian rounding and its applications to constraint satisfaction problems, 2018. ArXiv:1812.07769

work page arXiv 2018
[3]

Braverman, K

M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The G rothendieck constant is strictly smaller than K rivine's bound. Forum Math. Pi, 1:e4, 42, 2013

work page 2013
[4]

Eldan and A

R. Eldan and A. Naor. Krivine diffusions, 2014. Preprint

work page 2014
[5]

Feige and G

U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT . Random Structures Algorithms, 20(3):403--440, 2002. Probabilistic methods in combinatorial optimization

work page 2002
[6]

Grothendieck

A. Grothendieck. R\' e sum\' e de la th\' e orie m\' e trique des produits tensoriels topologiques. Bol. Soc. Mat. S\ a o Paulo , 8:1--79, 1953

work page 1953
[7]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115--1145, 1995

work page 1995
[8]

S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the T hirty- F ourth A nnual ACM S ymposium on T heory of C omputing , pages 767--775. ACM, New York, 2002. doi:10.1145/509907.510017

work page doi:10.1145/509907.510017 2002
[9]

S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX - CUT and other 2-variable CSP s? SIAM J. Comput., 37(1):319--357, 2007

work page 2007
[10]

J.-L. Krivine. Sur la constante de G rothendieck. C. R. Acad. Sci. Paris S\' e r. A-B , 284(8):A445--A446, 1977

work page 1977
[11]

Karatzas and S

I. Karatzas and S. E. Shreve. Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. ISBN 0-387-97655-8. doi:10.1007/978-1-4612-0949-2

work page doi:10.1007/978-1-4612-0949-2 1991
[12]

H. Kunita. Stochastic differential equations and stochastic flows of diffeomorphisms. In \' E cole d'\' e t\' e de probabilit\' e s de S aint- F lour, XII ---1982 , volume 1097 of Lecture Notes in Math., pages 143--303. Springer, Berlin, 1984. doi:10.1007/BFb0099433

work page doi:10.1007/bfb0099433 1982
[13]

Lindenstrauss and A

J. Lindenstrauss and A. Pe czy\' n ski. Absolutely summing operators in L_ p -spaces and their applications. Studia Math., 29:275--326, 1968

work page 1968
[14]

Naor and O

A. Naor and O. Regev. Krivine schemes are optimal. Proc. Amer. Math. Soc., 142(12):4315--4320, 2014

work page 2014
[15]

B. ksendal. Stochastic differential equations. Universitext. Springer-Verlag, Berlin, sixth edition, 2003. ISBN 3-540-04758-1. doi:10.1007/978-3-642-14394-6. An introduction with applications

work page doi:10.1007/978-3-642-14394-6 2003
[16]

G. Pisier. Grothendieck's theorem, past and present. Bull. Amer. Math. Soc. (N.S.), 49(2):237--323, 2012

work page 2012
[17]

Raghavendra

P. Raghavendra. Optimal algorithms and inapproximability results for every CSP ? [extended abstract]. In S TOC '08 , pages 245--254. ACM, New York, 2008. doi:10.1145/1374376.1374414

work page doi:10.1145/1374376.1374414 2008
[18]

Raghavendra and D

P. Raghavendra and D. Steurer. How to round any csp. In In Proc. 50th IEEE Symp. on Foundations of Comp. Sci. 2009

work page 2009
[19]

Raghavendra and D

P. Raghavendra and D. Steurer. Towards computing the G rothendieck constant. In Proceedings of the T wentieth A nnual ACM - SIAM S ymposium on D iscrete A lgorithms , pages 525--534. SIAM, Philadelphia, PA, 2009

work page 2009
[20]

B. S. Tsirelson. Quantum analogues of B ell's inequalities. T he case of two spatially divided domains. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 142:174--194, 200, 1985. Problems of the theory of probability distributions, IX

work page 1985

[1] [1]

P. Austrin. Towards sharp inapproximability for any 2- CSP . SIAM J. Comput., 39(6):2430--2463, 2010

work page 2010

[2] [2]

Abbasi-Zadeh, N

S. Abbasi-Zadeh, N. Bansal, G. Guruganesh, A. Nikolov, R. Schwartz, and M. Singh. Sticky brownian rounding and its applications to constraint satisfaction problems, 2018. ArXiv:1812.07769

work page arXiv 2018

[3] [3]

Braverman, K

M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The G rothendieck constant is strictly smaller than K rivine's bound. Forum Math. Pi, 1:e4, 42, 2013

work page 2013

[4] [4]

Eldan and A

R. Eldan and A. Naor. Krivine diffusions, 2014. Preprint

work page 2014

[5] [5]

Feige and G

U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT . Random Structures Algorithms, 20(3):403--440, 2002. Probabilistic methods in combinatorial optimization

work page 2002

[6] [6]

Grothendieck

A. Grothendieck. R\' e sum\' e de la th\' e orie m\' e trique des produits tensoriels topologiques. Bol. Soc. Mat. S\ a o Paulo , 8:1--79, 1953

work page 1953

[7] [7]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115--1145, 1995

work page 1995

[8] [8]

S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the T hirty- F ourth A nnual ACM S ymposium on T heory of C omputing , pages 767--775. ACM, New York, 2002. doi:10.1145/509907.510017

work page doi:10.1145/509907.510017 2002

[9] [9]

S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX - CUT and other 2-variable CSP s? SIAM J. Comput., 37(1):319--357, 2007

work page 2007

[10] [10]

J.-L. Krivine. Sur la constante de G rothendieck. C. R. Acad. Sci. Paris S\' e r. A-B , 284(8):A445--A446, 1977

work page 1977

[11] [11]

Karatzas and S

I. Karatzas and S. E. Shreve. Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. ISBN 0-387-97655-8. doi:10.1007/978-1-4612-0949-2

work page doi:10.1007/978-1-4612-0949-2 1991

[12] [12]

H. Kunita. Stochastic differential equations and stochastic flows of diffeomorphisms. In \' E cole d'\' e t\' e de probabilit\' e s de S aint- F lour, XII ---1982 , volume 1097 of Lecture Notes in Math., pages 143--303. Springer, Berlin, 1984. doi:10.1007/BFb0099433

work page doi:10.1007/bfb0099433 1982

[13] [13]

Lindenstrauss and A

J. Lindenstrauss and A. Pe czy\' n ski. Absolutely summing operators in L_ p -spaces and their applications. Studia Math., 29:275--326, 1968

work page 1968

[14] [14]

Naor and O

A. Naor and O. Regev. Krivine schemes are optimal. Proc. Amer. Math. Soc., 142(12):4315--4320, 2014

work page 2014

[15] [15]

B. ksendal. Stochastic differential equations. Universitext. Springer-Verlag, Berlin, sixth edition, 2003. ISBN 3-540-04758-1. doi:10.1007/978-3-642-14394-6. An introduction with applications

work page doi:10.1007/978-3-642-14394-6 2003

[16] [16]

G. Pisier. Grothendieck's theorem, past and present. Bull. Amer. Math. Soc. (N.S.), 49(2):237--323, 2012

work page 2012

[17] [17]

Raghavendra

P. Raghavendra. Optimal algorithms and inapproximability results for every CSP ? [extended abstract]. In S TOC '08 , pages 245--254. ACM, New York, 2008. doi:10.1145/1374376.1374414

work page doi:10.1145/1374376.1374414 2008

[18] [18]

Raghavendra and D

P. Raghavendra and D. Steurer. How to round any csp. In In Proc. 50th IEEE Symp. on Foundations of Comp. Sci. 2009

work page 2009

[19] [19]

Raghavendra and D

P. Raghavendra and D. Steurer. Towards computing the G rothendieck constant. In Proceedings of the T wentieth A nnual ACM - SIAM S ymposium on D iscrete A lgorithms , pages 525--534. SIAM, Philadelphia, PA, 2009

work page 2009

[20] [20]

B. S. Tsirelson. Quantum analogues of B ell's inequalities. T he case of two spatially divided domains. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 142:174--194, 200, 1985. Problems of the theory of probability distributions, IX

work page 1985