Strong Low Degree Hardness for the Number Partitioning Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910969731481600 |
|---|---|
| author | Mallarapu, Rushil Sellke, Mark |
| author_facet | Mallarapu, Rushil Sellke, Mark |
| contents | 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^{-Θ(\log^2 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20607 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strong Low Degree Hardness for the Number Partitioning Problem Mallarapu, Rushil Sellke, Mark Statistics Theory Computational Complexity Data Structures and Algorithms Probability 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^{-Θ(\log^2 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. |
| title | Strong Low Degree Hardness for the Number Partitioning Problem |
| topic | Statistics Theory Computational Complexity Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2505.20607 |