Ground-State Statistics of Sparse Max-Cut at 10⁸ to 10¹⁰ Spins: Extrapolations Bracket the Parisi Constant
Converged anneals at 10⁸ to 10¹⁰ spins on 8×H100, with independent CPU recounts at 10¹⁰ and overlaps between independent solutions computed over all 10⁹ spins.
0.738–0.776extrapolated (c − ½)√d at infinite degree from converged runs; Parisi P* = 0.7632
0.00011 ppstandard deviation of the cut over 15 runs at N = 10⁹ (79.5954–79.5958%)
h = 0.49997between two equal-cut solutions of one 10¹⁰-spin instance
2.66 ppannealed vs greedy-quench branch at N = 10⁹, both recounted
- (c − ½)√d rises from 0.683 (d = 3) to 0.745 (d = 16); extrapolations bracket Parisi: 0.738–0.776 vs 0.7632
- Self-averaging: sd 0.00011 pp (15 runs, 10⁹); 0.0027 pp (4 instances, 10¹⁰)
- Equal cuts from uncorrelated configurations (h = 0.49997 at 10¹⁰)
- Annealed 79.596% vs greedy-quench 76.937% at 10⁹; the cooling rate selects the branch
- Planted structure recovered above a sharp, size-independent f_c = 0.488–0.496 (N = 2k to 128k)