December 23, 2025
Heads, tails & hot takes
Proving Bounds for the Randomized MaxCut Approximation Algorithm in Lean4
Lean dev proves coin-flip cut; fans cheer, skeptics yawn
TLDR: A developer proved a coin-flip MaxCut in Lean4 achieves half the edges on average. The crowd split between applauding formal verification and mocking the “obvious” result, with nitpicks over definitions and memes about launching Coin-as-a-Service—proofs spark joy, and snark.
A developer just formalized the classic “flip every node like a coin” trick for the MaxCut problem in the Lean4 proof assistant—and the comments are pure chaos. The algorithm is simple: randomly split the graph’s points into two groups, and you’ll cut about half the edges on average. Some readers swooned over seeing math-meets-code in Lean4 and mathlib, calling it “proofs as code, vibes as theorem.” Others rolled their eyes so hard they saw bipartite graphs, blasting it as textbook-level flexing.
Strong opinions flew fast: formal verification fans praised turning “we think it works” into “it really, provably does.” Skeptics countered with “Congrats on proving the obvious,” and nitpickers pounced on the α-approx definition and the “Rocq vs Coq” name drop. A mini flamewar erupted over expectation vs guarantee—does “half on average” help anyone on a bad day? Meanwhile, code sleuths roasted the placeholder line “disjoint := b,” dubbing it the “b is for vibes” theorem, and joked that “by grind” is just hitting autopilot. Memes landed hard: “Coin-as-a-Service,” “linearity of expectation is my cheat code,” and “I deployed the random cut; my pager deployed me.” In short: formal methods got a win, and the comment section cut deeper than the algorithm.
Key Points
- •Presents a simple randomized algorithm for MaxCut: independently assign each vertex to one of two partitions with 50% probability.
- •Shows informally that each edge is cut with probability 1/2, so the expected cut size is |E|/2, giving a 1/2-approximation in expectation.
- •Notes that |E| ≥ |C*| for any graph, with equality when the graph is bipartite, leading to E[|C|] ≥ |C*|/2.
- •Begins a Lean formalization by defining a Cut structure with partitions A and B, and proof obligations that they are disjoint and cover all vertices.
- •Implements helper functions in Lean (edgeInCut, size, ofAssignment) to determine cut membership, compute size, and construct cuts from boolean assignments.