Strong Low Degree Hardness for the Number Partitioning Problem

2025/05/27 by Rushil Mallarapu, Mark Sellke, Mallarapu, Rushil +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #Statistics Theory (math.ST) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2505.20607

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the number partitioning problem (NPP) one aims to partition a given set of N real numbers into two subsets with approximately equal sum. The NPP is a well-studied optimization problem and is famous for possessing a statistical-to-computational gap: when the N numbers to be partitioned are i.i.d. standard gaussian, the optimal discrepancy is 2^-Θ(N) with high probability, but the best known polynomial-time algorithms only find solutions with a discrepancy of 2^{-Θ(log2 N)}. This gap is a common feature in optimization problems over random combinatorial structures, and indicates the need for a study that goes beyond worst-case analysis. We provide evidence of a nearly tight algorithmic barrier for the number partitioning problem. Namely we consider the family of low coordinate degree algorithms (with randomized rounding into the Boolean cube), and show that degree D algorithms fail to solve the NPP to accuracy beyond 2^{-\widetilde O(D)}. According to the low degree heuristic, this suggests that simple brute-force search algorithms are nearly unimprovable, given any allotted runtime between polynomial and exponential in N. Our proof combines the isolation of solutions in the landscape with a conditional form of the overlap gap property: given a good solution to an NPP instance, slightly noising the NPP instance typically leaves no good solutions near the original one. In fact our analysis applies whenever the N numbers to be partitioned are independent with uniformly bounded density.

Citations

• Symmetric Perceptrons, Number Partitioning and Lattices
• Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
• Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms
• Some easy optimization problems have the overlap-gap property
• Hardness of sampling solutions from the Symmetric Binary Perceptron
• Discrepancy Algorithms for the Binary Perceptron
• Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
• Shattering in the Ising Pure p-Spin Model
• The Algorithmic Phase Transition of Random Graph Alignment Problem
• Shattering in Pure Spherical Spin Glasses
• Algorithmic Threshold for Multi-Species Spherical Spin Glasses
• Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
• Algorithms and Barriers in the Symmetric Binary Perceptron Model
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
• Algorithmic Obstructions in the Random Number Partitioning Problem
• Optimal Low-Degree Hardness of Maximum Independent Set
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• The Overlap Gap Property and Approximate Message Passing Algorithms for\n p-spin models
• Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design
• Subexponential-Time Algorithms for Sparse PCA
• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• The Kikuchi Hierarchy and Tensor PCA
• Artificial Immune Systems Can Find Arbitrarily Good Approximations for\n the NP-Hard Number Partitioning Problem
• The power of sum-of-squares for detecting hidden structures
• Sum of squares lower bounds for refuting any CSP
• Nearly Random Designs with Greatly Improved Balance
• Number Balancing is as hard as Minkowski's Theorem and Shortest Vector
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Finding a Large Submatrix of a Gaussian Random Matrix
• Tensor principal component analysis via sum-of-squares proofs
• Sum-of-squares lower bounds for planted clique
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden\n Submatrix Problems
• Derrida's random energy models. From spin glasses to the extremes of correlated random fields
• Limits of local algorithms over sparse random graphs
• Analysis of Boolean Functions
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Proof of the local REM conjecture for number partitioning II: growing energy scales
• Clustering of solutions in the random satisfiability problem
• Proof of the local REM conjecture for number partitioning I: Constant\n energy scales
• Universality in the level statistics of disordered systems
• The Easiest Hard Problem: Number Partitioning
• A physicist's approach to number partitioning
• Bounds on Multiprocessing Timing Anomalies

Cited by

• Sharp Online Hardness for Large Balanced Independent Sets

Related

• Algorithmic Obstructions in the Random Number Partitioning Problem
• The Easiest Hard Problem: Number Partitioning
• A physicist's approach to number partitioning
• Planted Random Number Partitioning Problem
• Sampling and Complexity of Partition Function