{"id":"d4417864-4232-4f27-b6a2-fe445c2ff5fc","arxiv_id":"2505.20607","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Low coordinate degree algorithms with randomized rounding fail to solve random number partitioning near-optimally, giving strong low-degree hardness for this problem.","lead":"This paper shows that a broad family of fast computer methods, called low-degree algorithms, cannot find near-perfect splits of a random list of numbers into two equal-sum groups. If correct, it supports the idea that the huge gap between mathematically possible and computationally findable solutions in this classic problem is real.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.13's proof defines K = max(log^2 N, Σ I_{x,i}) but then asserts K ≤ log^2 N; Lemma 2.11 only gives divergence, and Lemma 2.12 would require E >> K log N, so the 2^{-K} rounding bound is unsupported for part (b).","rationale":"The reader's weakest assumption correctly identifies the K ≤ log^2 N assertion. I read Section 2.6 carefully and confirm the issue is not a transcription typo: the proof defines K as a max, then uses it as an upper bound on the resampled coordinates in the isolation lemma. Lemma 2.11 gives the opposite control (lower bound on divergence), so the proof is internally inconsistent. I add one refinement: even if K were capped at log^2 N, the algebra in the displayed bound is off by a factor of log N, so the stated energy assumption E = ω(log^2 N) is not sufficient for Lemma 2.12. This makes the gap more severe than a simple max/min slip, though it does not necessarily falsify Theorem 1.4; a separate treatment of the large-K regime (e.g., a direct first-moment bound when the rounded point is nearly independent of g) may repair it. I therefore agree with the conditional verdict. I credit the paper for the non-rounded LCD proof and the LDP proof, which are independent of Theorem 2.13 and appear to go through; my concern is isolated to the rounding reduction.","tokens_in":25493,"tokens_out":14256,"duration_ms":141603,"concrete_test":"Fix A(g) to be the constant vector 0 on a block of size log^2 N and +1 elsewhere (coordinate degree 0, E||A||^2 ≤ N). Then p_i = 1/2 on the block, Σ p_i = Θ(log^2 N) = ω(1), and K = Σ I_{x,i} = Θ(log^2 N) with high probability; taking the block of size N instead gives K = N, a direct counterexample to the asserted K ≤ log^2 N. For E = ω(log^2 N), compute the right side of (2.12) with k = K: it is exp2(-E + O(K log N)) = exp2(-E + O(log^3 N)), which is not o(1) for E ∈ ω(log^2 N) ∩ o(log^3 N). Also compute P(tilde A ∈ S(E;g)) directly: since tilde A is independent of g, it is Θ(2^{-E}/√N) = o(1). This shows the conclusion can hold while the isolation argument fails, and therefore Section 2.6 must supply a separate large-K argument. If no such argument is provided, Theorem 1.4(b) is unproved in this regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.6, proof of Theorem 2.13: after Lemma 2.10, K is defined as max(log^2 N, Σ_i I_{x,i}). The next sentence asserts \"we know K ... is bounded as 1 << K ≤ log^2 N\". This is self-contradictory: K ≥ log^2 N by definition, and Lemma 2.11 only guarantees the resampled count Σ_i I_{x,i} diverges in probability; it can exceed log^2 N (e.g., p_i = 1/2 for all i gives K = N). The subsequent application of Lemma 2.12 requires E >> k log N with k = K, hence E >> K log N. Even granting 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 = O(log^3 N), not O(log^2 N), so -E + O(log^3 N) need not tend to -∞ when E = ω(log^2 N). Thus the proof does not establish the 2^{-K} bound in the parameter range of Theorem 1.4(b). The non-rounded LCD result (Section 2.4) and the LDP result (Theorem 1.3) do not rely on this step and appear sound; the gap is specific to the randomized-rounding reduction, which is essential for Theorem 1.4.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":25773,"tokens_out":24736,"duration_ms":230617,"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":[{"comment":"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.","section":"Section 2.6, proof of Theorem 2.13"},{"comment":"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.","section":"Section 2.6, proof of Theorem 2.13 (displayed inequality)"},{"comment":"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.","section":"Proof of Theorem 1.4, final paragraph"}],"minor_comments":[{"comment":"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.","section":"Lemma 2.4"},{"comment":"The displayed derivation contains typos: Q is E[Q(ω)], not E[q(ω)], and the final equality should be q^2, not p^2.","section":"Remark 2.6"},{"comment":"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.","section":"Theorem 2.13"},{"comment":"The notation 'log3 2(N/E)' is ambiguous; it should be written as log_2^3(N/E) or the base should be clarified.","section":"Section 2.4, proof of Theorem 1.4"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the non-rounded portions are sound. The randomized-rounding step (Theorem 2.13) is the central technical gap; it affects the headline Theorem 1.4. I believe a repair is plausible but may require more than a local fix: the K definition, the parameter regime, and the final reduction in the proof of Theorem 1.4 all need to be reworked. In its current form, I cannot recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a clean conditional-OGP argument for the NPP and proves low-degree hardness for non-rounded LCD algorithms and LDP algorithms across a wide energy range. The exposition is strong, and the connection to [HS25b] is handled explicitly. The LDP and non-rounded LCD results appear sound, and the conditional landscape obstruction (Lemma 2.4) is a nice contribution.\n\nThe problem is the randomized rounding step, Theorem 2.13, which is essential for Theorem 1.4. In the proof, K is defined as max(log^2 N, sum_i I_{x,i}), and then the next sentence asserts K ≤ log^2 N. That's self-contradictory. Lemma 2.11 merely guarantees the resampled count diverges in probability; it can easily exceed log^2 N. Additionally, the algebra in the bound is off: if K ≤ log^2 N, then O(K log N) is O(log^3 N), not O(log^2 N), so the displayed exp2(-E + O(log^2 N)) is not justified. Both issues land on the parameter range of Theorem 1.4(b), where E = ω(log^2 N). The non-rounded LCD result (Prop 2.9) and LDP result don't rely on this step. So the paper's main theorem should be viewed as unproven.\n\nThat said, the issue looks repairable — e.g., using min instead of max, or splitting on whether the resampled count is large and handling the large case separately. It's not a fundamental flaw in the conditional OGP idea. The final paragraph of Theorem 1.4's proof also deserves clarification; the way r is sent to infinity is terse.\n\nWho gets value: researchers in low-degree hardness and random discrepancy. I'd want a referee to run a careful pass on Section 2.6 before accepting the paper. My recommendation: send to peer review with major revision required, not a desk reject. The framework and non-rounded results are solid; the rounding step needs a fix.","headline":"The paper's conditional-OGP machinery is real, but the randomized rounding step that carries Theorem 1.4 is broken as written.","tokens_in":26357,"tokens_out":2158,"would_cite":true,"duration_ms":21669,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","60G15","82B44","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["number partitioning","low coordinate degree","statistical-to-computational gap","overlap gap property","randomized rounding","discrepancy minimization","Gaussian disorder","low-degree heuristic"],"falsifier":"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$.","tokens_in":25235,"feed_emoji":"⚖️","tokens_out":8777,"duration_ms":80995,"temperature":0.7,"pith_summary":"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$.","feed_headline":"Low-degree algorithms fail to beat brute force on number partitioning","feed_subtitle":"Gaussian instances hide 2^{-N} solutions; low-degree search stalls at 2^{-O(D)}. Brute force is nearly optimal.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the statistical optimum discrepancy $\\Theta(\\sqrt{N}2^{-N})$, the target the paper contrasts with algorithmic performance.","marker":"[Kar+86]"},{"why":"Provides the best known polynomial-time differencing method achieving $2^{-O(\\log^2 N)}$, the computational baseline.","marker":"[KK83]"},{"why":"Gives the prior overlap gap property analysis of the NPP that this paper extends with a conditional obstruction.","marker":"[GK23]"},{"why":"Supplies the strong low degree hardness definition and the positive correlation lemma used to pass from one-instance to correlated-pair success.","marker":"[HS25b]"},{"why":"Supplies the stability argument for low-coordinate-degree functions under resampling, used in Proposition 1.6.","marker":"[Gam+22]"},{"why":"Provides the exercise bounding inner products of coordinate-degree functions on correlated Gaussian pairs, the analytical core of the stability estimate.","marker":"[O'D14]"},{"why":"Articulates the low-degree heuristic linking degree-$D$ algorithms to $\\exp(O(D))$ time, which gives the paper's algorithmic upshot.","marker":"[KWB19]"}],"fun_headline_variants":["Low-degree algorithms can't outdo brute force on NPP","Degree D search caps at 2^{-O(D)} for number partitioning","Hardness barrier: low-degree algorithms hit 2^{-O(D)}","For NPP, low-degree methods can't approach 2^{-N}","No low-degree shortcut for number partitioning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Low-degree algorithms can't outdo brute force on NPP","Degree D search caps at 2^{-O(D)} for number partitioning","Hardness barrier: low-degree algorithms hit 2^{-O(D)}","For NPP, low-degree methods can't approach 2^{-N}","No low-degree shortcut for number partitioning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000705,"raw_usage":{"total_tokens":3218,"prompt_tokens":1024,"completion_tokens":2194,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":2106}},"tokens_in":640,"tokens_out":2194,"duration_ms":27250,"temperature":1.0,"reasoning_tokens":2106,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:51:59.353248+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}