Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Strong Low Degree Hardness for the Number Partitioning Problem

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that low coordinate degree algorithms, after randomized rounding, fail to find near-optimal partitions of random Gaussian number partitioning instances at almost all energy levels between the statistical and…

desk verdict The paper's conditional-OGP machinery is real, but the randomized rounding step that carries Theorem 1.4 is broken as written. read the letter →

arxiv 2505.20607 v1 pith:HBBG65NP submitted 2025-05-27 math.ST cs.CCcs.DSmath.PRstat.TH

Rushil Mallarapu , Mark Sellke This is my paper · ORCID
classification math.STcs.CCcs.DSmath.PRstat.TH MSC 68Q1760G1582B4490C27
keywords numberpartitioninglowcoordinatedegreestatistical-to-computationalgapoverlappropertyrandomizedroundingdiscrepancyminimizationGaussiandisorderlow-degreeheuristic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Number partitioning asks to split $N$ given numbers into two groups with sums as close as possible. For independent standard Gaussian inputs, the optimal split has discrepancy $2^{-\Theta(N)}$ with high probability, but the best known polynomial-time algorithms only reach discrepancy $2^{-\Theta(\log^2 N)}$. This paper tries to prove that the gap is not an artifact of missing algorithms: any algorithm whose output depends on at most $D$ coordinates, after randomized rounding to a partition, fails to find partitions of energy $E$ (discrepancy $2^{-E}$) for essentially all $E$ between the computational and statistical thresholds, whenever $D$ is small enough relative to $E$. If the low-degree heuristic is right, the practical conclusion is that brute-force search over $E$ coordinates is nearly unimprovable for every runtime between polynomial and exponential in $N$.

What carries the argument

The argument rests on a conditional form of the overlap gap property. Given a good solution $x$ to an instance $g$, slightly resample a few coordinates to form a correlated instance $g'$; with high probability no good solution to $g'$ lies within distance $2\sqrt{\eta N}$ of $x$ (Lemma 2.4). A stability estimate (Proposition 1.6) shows a coordinate-degree $D$ algorithm's outputs on $g$ and $g'$ are close with high probability, so it cannot solve both, and a positive-correlation lemma (Lemma 2.5) converts this into failure on a single instance. Randomized rounding is handled by the isolation lemma “Solutions Repel” (Lemma 2.12): with high probability no two $E$-good solutions lie within $2\sqrt{k}$ sign flips when $E \gg k \log N$, so a rounding that resamples many coordinates lands in a subcube containing at most one solution.

What would settle it

Run the randomized rounding of the paper on a concrete low-coordinate-degree algorithm for Gaussian NPP instances with $E = C\log^2 N$, and record the number $K$ of resampled coordinates on the event that the rounded partition has discrepancy at most $2^{-E}$. If $K > \log^2 N$ occurs with probability not $o(1)$ on that event, the isolation step of Theorem 2.13 fails. Alternatively, test Lemma 2.12 directly by checking whether two distinct partitions with discrepancy at most $2^{-E}$ ever appear within $2\sqrt{\log^2 N}$ sign flips of each other at $E = C\log^2 N$; the lemma only rules this out when $E \gg k \log N$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.4: for a standard Gaussian NPP instance, every coordinate degree $D$ algorithm $A$ with $\mathbb{E}\|A(g)\|^2 \le C N$, after randomized rounding into the Boolean cube, has $P(\widetilde{A}(g) \in S(E;g)) = o(1)$ whenever (a) $E = \delta N$ and $D \le o(N)$, or (b) $\omega(\log^2 N) \le E \le o(N)$ and $D \le o(E/\log^2(N/E))$. In other words, degree-$D$ low coordinate degree algorithms cannot find partitions with discrepancy $2^{-E}$ in these regimes. The paper also proves a low polynomial degree version (Theorem 1.3) with the stronger degree allowance $D \le o(2^{E/4})$, and observes that the coordinate-degree proof extends verbatim to any independent inputs with uniformly bounded density.

Load-bearing premise

The proof of Theorem 2.13 assumes the number of coordinates $K$ resampled by randomized rounding satisfies $K \le \log^2 N$ at all times, but the argument only proves $K$ diverges to infinity; if $K$ can exceed $\log^2 N$, the rounded output may lie in a subcube containing several solutions and the $2^{-K}$ probability bound collapses.

Editorial extensions

If this is right

  • At any energy $E$ covered by Theorem 1.4, only algorithms whose outputs genuinely depend on more than $D$ coordinates can have non-negligible success probability, so good NPP algorithms must be “truly global.”
  • Under the low-degree heuristic, solving the NPP to energy $E$ requires time $\exp(\Omega(E))$; restricted brute-force search over $E$ coordinates achieves this, making the energy-degree tradeoff tight along the whole range $1 \ll E \le N$.
  • The hardness is not special to Gaussians: the same proof works for any independent inputs with uniformly bounded density.
  • For polynomial degree, the failure is even more pronounced: degree $D \le o(2^{E/4})$ algorithms fail, so low-degree polynomials are a poor proxy for efficient algorithms for the NPP.
  • The statistical-to-computational gap for the NPP is therefore not a lack of clever algorithms but a geometric barrier in the solution landscape.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof's most delicate step is the claim that randomized rounding resamples at most $\log^2 N$ coordinates; if that bound fails, the subcube containing the rounded output may hold multiple solutions and the argument does not go through.
  • A natural stress test is to measure, for a concrete low-degree algorithm at energy $E = C\log^2 N$, the distribution of the number of resampled coordinates on the event that the rounded output is $E$-good.
  • The conditional OGP used here is weaker than the global OGP of earlier work; this suggests similar conditional obstructions may extend to vector balancing or other random optimization problems with brittle solutions.
  • If the barrier is genuine, alternative algorithmic approaches for NPP should be judged against the energy-degree tradeoff $D \approx E$, not merely against worst-case NP-hardness.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the number partitioning problem (NPP) for i.i.d. Gaussian inputs (and independent inputs with uniformly bounded density). It defines the energy of a partition x by E(x;g) = -log_2 |<g,x>| and the solution set S(E;g), and proves strong low degree hardness (SLDH) in the sense of [HS25b]. Theorem 1.3 shows that low-degree polynomial algorithms with D = o(2^{E/4}) fail to find solutions of energy E ≥ ω(log N). Theorem 1.4 shows that low-coordinate-degree algorithms, after randomized rounding into the Boolean cube, fail to find solutions of energy E in the ranges (a) E = δN with D = o(N), or (b) ω(log^2 N) ≤ E ≤ o(N) with D = o(E/log^2(N/E)). The proof combines a conditional overlap gap property (Lemma 2.4), a positive-correlation lemma (Lemma 2.5), a solution-isolation lemma (Lemma 2.12), and the stability of low-degree algorithms (Proposition 1.6). The paper also gives a heuristic argument for near-optimality of the energy-degree tradeoff (Section 1.2).

Significance. The conditional-OGP approach is a novel and potentially fruitful way to prove algorithmic hardness for the NPP, a problem with a wide statistical-to-computational gap. If the proof were complete, Theorem 1.4 would give a nearly tight energy-degree tradeoff for low coordinate degree algorithms, providing rigorous support for the low-degree heuristic in this problem. The proof of Theorem 1.3 and the non-rounded LCD result in Section 2.4 appear sound and are carefully presented; the stability and correlation lemmas are standard but are reproduced with sufficient detail. The main weakness is the randomized-rounding reduction (Theorem 2.13), which contains several unsupported steps and is essential for the headline result Theorem 1.4. Because the gap is localized to this step, the result is likely repairable, but the current manuscript does not establish Theorem 1.4 as written.

major comments (3)
  1. [Section 2.6, proof of Theorem 2.13] The proof defines K := max(log^2 N, sum_i I_{x,i}) and then immediately asserts that 'we know K, which is at least the number of coordinates which are resampled, is bounded as 1 << K <= log^2 N'. This is self-contradictory: K >= log^2 N by definition, and Lemma 2.11 guarantees only that the number of resampled coordinates diverges in probability, with no upper bound. Consequently the subcube dimension K is not established to be O(log^2 N), and the application of Lemma 2.12 (which requires E >> k log N with k = K) is not justified. This invalidates the claimed 2^{-K} bound in Theorem 2.13.
  2. [Section 2.6, proof of Theorem 2.13 (displayed inequality)] Even if one granted K <= log^2 N, the displayed bound exp2(-E + O(K log N)) <= exp2(-E + O(log^2 N)) is algebraically wrong: K log N is O(log^3 N), not O(log^2 N). The conclusion that this quantity is o(1) therefore requires E >> log^3 N, whereas Theorem 2.13 and Theorem 1.4(b) only assume E >= ω(log^2 N). The argument fails in the intermediate range, for example E = log^2 N log log N.
  3. [Proof of Theorem 1.4, final paragraph] The reduction to Theorem 2.13 is not justified. The event {Ã(g) in S(E;g), Â_r(g) not in S(E;g)} is asserted to be o_{r→∞}(1) 'since ||x - x*||_2 <= ||x - x*||_1', but this inequality is irrelevant: x is the raw real-valued output, and the distance from x to its sign x* is not what controls the success of randomized rounding or of the locally-improved algorithm. The proof does not explain how the complementary case where the number of flipped coordinates is bounded (so that Theorem 2.13's assumption sum_i p_i(x) = ω(1) fails) is handled; Proposition 2.9 concerns Â_r, not the deterministic sign algorithm A*. This step requires a substantially expanded argument.
minor comments (5)
  1. [Lemma 2.4] In the resampled case, the representation g' = g_J + ̃g_J should read g' = g_J + ̃g_{J^c}, since J is the set of coordinates where g' equals g; the current notation is confusing and inconsistent with the variance statement that follows.
  2. [Remark 2.6] The displayed derivation contains typos: Q is E[Q(ω)], not E[q(ω)], and the final equality should be q^2, not p^2.
  3. [Theorem 2.13] The conclusion that 'the probability that any of the ̃x is in S(E;g) is bounded by 2^{-K}' should include the o(1) error from the event that more than one solution exists in the subcube; as written, the bound is missing this additive term.
  4. [Section 2.4, proof of Theorem 1.4] The notation 'log3 2(N/E)' is ambiguous; it should be written as log_2^3(N/E) or the base should be clarified.
  5. [Throughout] The symbol J is used for several different sets (the kept coordinates in resampling, the differing coordinates in Lemma 2.12, and the set of resampled coordinates in Theorem 2.13); harmonizing this notation would improve readability.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the NPP-specific landscape and rounding arguments are self-contained; flagged issues are correctness gaps, not circularities.

full rationale

The paper's central claim (Theorem 1.4) is derived from ingredients developed inside the paper: the conditional OGP (Lemma 2.4), the positive-correlation lemma (Lemma 2.5, whose proof is given), the isolation lemma (Lemma 2.12), and the rounding reduction (Lemmas 2.10-2.11 and Theorem 2.13). Reused material from [HS25b] - the SLDH definition (Definition 1.2) and the stability bound (Proposition 1.6) - is either reproduced with proof or cited as a standard tool and is not load-bearing; the same authors' prior work does not force the NPP-specific result. No parameter is fitted and then renamed as a prediction; no definition is equivalent to the target by construction. The only notable flaw is in the proof of Theorem 2.13 (Section 2.6): after defining K = max(log^2 N, sum_i I_{x,i}), the text asserts "we know K ... is bounded as 1 << K <= log^2 N", but K is at least log^2 N by definition and Lemma 2.11 only guarantees divergence, not an upper bound of log^2 N. Moreover, the displayed estimate exp2(-E + O(K log N)) <= exp2(-E + O(log^2 N)) would require K log N = O(log^2 N), which fails for K = log^2 N (it is log^3 N). This is an unsupported proof step and a correctness risk for part (b) of Theorem 1.4, but it is not a circularity: it does not make the conclusion equivalent to an input by construction. The non-rounded LCD result (Section 2.4) and the LDP result (Theorem 1.3) do not rely on this step, so the central derivation is otherwise self-contained, and the self-citations in the paper are minor and non-load-bearing.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No fitted parameters or invented entities. The proof assumes the input distribution has bounded density (Lemmas 2.1, 2.12), the standard L2-stability of low-degree functions (Prop 1.6), and the low-degree heuristic for interpretation. The unsupported K <= log^2 N step in Theorem 2.13 is not a declared axiom; it is flagged as a red flag.

assumptions (3)
  • domain assumption The random inputs g_i are independent with uniformly bounded density (Gaussian in the main theorems).
    Lemma 2.1 and Lemma 2.12 require a uniform density bound to control the probability of near-zero inner products. The main theorem is stated for Gaussians; Remark 1.5 extends it to bounded densities.
  • standard math Low-degree functions are L2-stable under correlated or resampled inputs (Proposition 1.6, citing [O'D14, Exer. 8.18] and [HS25b, Prop. 1.7]).
    This is the key mechanism forcing stable algorithm outputs to be close on correlated instances. The paper reproduces the proof in the LCD case.
  • domain assumption The low-degree heuristic: degree-D algorithms are good proxies for e^{O~(D)}-time algorithms.
    The formal theorems are unconditional for the algorithm classes, but the title's claim of an 'algorithmic barrier' and the interpretation in Section 1.2 depend on this heuristic.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong Low Degree Hardness for the Number Partitioning Problem." pith.science (2026). https://pith.science/paper/HBBG65NP

@misc{pith2026250520607,
  author       = {Pith},
  title        = {Pith review of: Strong Low Degree Hardness for the Number Partitioning Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HBBG65NP}},
  note         = {Machine review of arXiv:2505.20607}
}
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^{-\Theta(N)}$ with high probability, but the best known polynomial-time algorithms only find solutions with a discrepancy of $2^{-\Theta(\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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

    math.ST 2025-06 accept novelty 2.0 of 10

    A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [2]

    Optimal low-degree hardness of maximum independent set,

    [Online]. Available: http:/ /arxiv.org/abs/2501.16517 [Wei22] A. S. Wein, “Optimal low-degree hardness of maximum independent set,” Mathematical Statistics and Learning, vol. 4, no. 3, pp. 221–251, 2022. [WEM19] A. S. Wein, A. El Alaoui, and C. Moore, “The Kikuchi hierarchy and tensor PCA,” in 2019 IEEE 60th Annual Symposium on Foundations of Computer Sci...

    arXiv 2022

  2. [2025]

    Tensor principal component analysis via sum-of-square proofs,

    [Online]. Available: http:/ /arxiv.org/abs/2501.06427 [HSS15] S. B. Hopkins, J. Shi, and D. Steurer, “Tensor principal component analysis via sum-of-square proofs,” in Conference on Learning Theory, 2015, pp. 956–1006. [Jer92] M. Jerrum, “Large Cliques Elude the Metropolis Process,” Random Structures & Algorithms, vol. 3, no. 4, pp. 347–359, Jan. 1992, do...

    arXiv 2015

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.