2005/01/31 by Christian Borgs, Jennifer Chayes, Borgs, Christian +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Statistical Mechanics (cond-mat.stat-mech) #Theoretical and Computational Physics #Topological and Geometric Data Analysis #cond-mat.dis-nn #cond-mat.stat-mech #math-ph #math.MP #math.PR
paper · pdf · doi:10.48550/arxiv.cond-mat/0501760
26 pages, no figures
openalex publication_date 2005/01/31 · arxiv created 2005/04/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The number partitioning problem is a classic problem of combinatorial\noptimization in which a set of n numbers is partitioned into two subsets such\nthat the sum of the numbers in one subset is as close as possible to the sum of\nthe numbers in the other set. When the n numbers are i.i.d. variables drawn\nfrom some distribution, the partitioning problem turns out to be equivalent to\na mean-field antiferromagnetic Ising spin glass. In the spin glass\nrepresentation, it is natural to define energies -- corresponding to the costs\nof the partitions, and overlaps -- corresponding to the correlations between\npartitions. Although the energy levels of this model are em a priori highly\ncorrelated, a surprising recent conjecture asserts that the energy spectrum of\nnumber partitioning is locally that of a random energy model (REM): the\nspacings between nearby energy levels are uncorrelated. In other words, the\nproperly scaled energies converge to a Poisson process. The conjecture also\nasserts that the corresponding spin configurations are uncorrelated, indicating\nvanishing overlaps in the spin glass representation. In this paper, we prove\nthese two claims, collectively known as the local REM conjecture.\n