Algorithmic obstructions in the random number partitioning problem

DOI10.1214/23-aap1953arXiv2103.01369MaRDI QIDQ6139686

Eren C. Kızıldağ, David Gamarnik

Publication date: 19 January 2024

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.01369

zbMATH Keywords

computational complexitystatistical physicsdiscrepancynumber partitioningmoment methodaverage-case hardnessrandomized controlled trialsfree energy wellsoverlap gap propertyoptimization landscape

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly Random Designs with Greatly Improved Balance
• Balancing Gaussian vectors
• Algorithmic thresholds for tensor PCA
• On the independence number of random graphs
• A note on the average-case behavior of a simple differencing method for partitioning
• On the independence and chromatic numbers of random regular graphs
• Information-theoretic thresholds from the cavity method
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Charting the replica symmetric phase
• Finding a large submatrix of a Gaussian random matrix
• Local algorithms for independent sets are half-optimal
• The overlap gap property in principal submatrix recovery
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Lower bounds for multicolor Ramsey numbers
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Universality in polytope phase transitions and message passing algorithms
• Large independent sets in regular graphs of large girth
• Suboptimality of local algorithms for a class of max-cut problems
• Limits of locally-globally convergent graph sequences
• The variation of the spectrum of a normal matrix
• Phase transition and finite-size scaling for the integer partitioning problem
• Entropy landscape of solutions in the binary perceptron problem
• Constructive Discrepancy Minimization for Convex Sets
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Integer feasibility of random polytopes
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Efficient noise-tolerant learning from statistical queries
• Recent developments in graph Ramsey theory
• Random-energy model: An exactly solvable model of disordered systems
• Constructive Discrepancy Minimization by Walking on the Edges
• On independent sets in random graphs
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• Proof of the local REM conjecture for number partitioning. II. Growing energy scales
• Six Standard Deviations Suffice
• Probabilistic analysis of optimum partitioning
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Large Cliques Elude the Metropolis Process
• Phase Transition in the Number Partitioning Problem
• Finite Sample Analysis of Approximate Message Passing Algorithms
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
• High-Dimensional Probability
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Sum of squares lower bounds for refuting any CSP
• State evolution for approximate message passing with non-separable functions
• Storage capacity in symmetric binary perceptrons
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Local optima of the Sherrington-Kirkpatrick Hamiltonian
• The freezing threshold for k-colourings of a random graph
• A CDMA multiuser detection algorithm on the basis of belief propagation
• The condensation transition in random hypergraph 2-coloring
• A Unifying Tutorial on Approximate Message Passing
• Hiding information and signatures in trapdoor knapsacks
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• On the solution‐space geometry of random constraint satisfaction problems
• Limits of local algorithms over sparse random graphs
• The condensation phase transition in random graph coloring
• Frozen 1-RSB structure of the symmetric Ising perceptron