{"id":"719a90a6-16b4-4471-ad21-84cdacf88dd9","arxiv_id":"2501.16517","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Assuming worst-case lattice hardness, no polynomial-time algorithm can solve SBP at kappa close to 1/sqrt(x) or NPP at kappa close to 2^{-log^3 m}.","lead":"This paper proves conditional average-case hardness for the symmetric binary perceptron and number partitioning problems: assuming worst-case lattice problems are hard to approximate, no efficient algorithm can find solutions at the statistically natural thresholds. It supplies the first worst-case-to-average-case reductions from standard lattice problems to these search problems, confirming the Gamarnik-Kizildag-Perkins-Xu conjecture up to lower-order terms.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Near-optimal SBP claim is unproven as written: the reduction's statistical-closeness bound is not negligible when m=2^{O(n^{3/(2c)})}.","rationale":"The reader's weakest assumption is the standard worst-case lattice hardness assumption, which is an external conditional premise and not a flaw in the reduction. My stress-test found a different, more concrete gap: the near-optimal SBP claim in Remark 1 uses m super-polynomial in n, while every statistical-closeness bound in the written proof is multiplied by m and decays in n. The arithmetic m e^{-ln^2 n} = exp(Θ(n^{3/(2c)}) - Θ(ln^2 n)) tends to infinity for c>3, so the reduction as written cannot justify calling the SBP solver on a nearly Gaussian input. This does not affect the polynomial-parameter statement of Theorem 3, where m=n^{Θ(1/ε)} and m e^{-ln^2 n}→0, nor the NPP theorem, which already uses σ2=ln m and has error m e^{-ln^2 m}. The issue is likely fixable by reducing from IncGDD_{4m ln m} and setting the smoothing error to e^{-ln^2 m}; the stated bound γ=2^{O(n^{3/(2c)})} absorbs this. Because the fix is plausible but not written, the verdict should remain conditional; I therefore do not move the reader's verdict. The disagreement is only about which concern is load-bearing: the lattice hardness assumption was not the point of failure in the written proof of the near-optimal SBP claim.","tokens_in":25507,"tokens_out":52976,"duration_ms":474134,"concrete_test":"Take c=4 and m=2^{n^{3/8}} in Remark 1. Recompute Proposition 1's total variation with the printed parameters σ1=r/(4m), γ=4m ln n, ε=e^{-ln^2 n}: mε is non-negligible, so A is not close to Gaussian. Then repeat with γ=4m ln m and ε=e^{-ln^2 m}, and verify the proof's final inequality ln m · n^{1/2}/(log(m/n))^{1+c} ≤ 1/(8n). If the repaired inequality holds, the claim is salvageable; if not, the near-optimal SBP statement needs a weaker κ or a different reduction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 in Section 3.1 proves Δ(tilde A, U) ≤ m e^{-ln^2 n}, and Lemma 8 is then invoked m times, so the total distance is again of order m e^{-ln^2 n}. This is negligible only when m is at most e^{o(ln^2 n)} in the lattice dimension n. Remark 1 sets m=2^{O(n^{3/(2c)})} for the near-optimal regime κ(x)=1/(√x log^{1+c}x); for fixed c>3 this is super-polynomial in n. With the parameters as printed (σ1=r/(4m), γ=4m ln n, ε_smooth=e^{-ln^2 n}), the product m e^{-ln^2 n}=exp(Θ(n^{3/(2c)})-Θ(ln^2 n)) diverges, so the matrix fed to the SBP oracle is not statistically close to the Gaussian distribution on which the solver is assumed to succeed. The near-optimal SBP theorem therefore does not follow from the written proof. The likely salvage is to reduce from IncGDD with γ=4m ln m instead of 4m ln n and to use smoothing error e^{-ln^2 m}; both preserve the stated bound γ=2^{O(n^{3/(2c)})}, and the total error becomes m e^{-ln^2 m}=negl(m). This parameter change must be checked against the norm bound, where σ2 becomes ln m.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves conditional average-case hardness for the symmetric binary perceptron (SBP) and the number partitioning problem (NPP), via worst-case to average-case reductions from lattice problems (IncGDD, and hence SIVP, GapCRP, and GDD) using Gaussian smoothing in the style of Micciancio-Regev. Theorem 3 gives a polynomial-time reduction to SBP with κ(x)=1/x^{1/2+ε} under polynomial lattice hardness assumptions; Theorem 4 gives a poly(m)-time reduction to NPP with κ(m)=2^{-log^{2+ε} m} under subexponential lattice hardness assumptions. The paper also claims, in Remark 1, a near-optimal SBP hardness statement with κ(x)=1/(√x log^{1+c} x) for c>3 under Assumption 2. Corollaries are drawn for the original GKPX22 conjecture and for near-tightness of the Karmarkar-Karp algorithm.","tokens_in":25766,"tokens_out":29805,"duration_ms":237111,"significance":"If the results hold, they resolve (up to lower-order terms) the conjecture of Gamarnik, Kızıldağ, Perkins and Xu that the Bansal-Spencer guarantee κ=Θ(1/√x) is the best achievable by efficient algorithms, and they show that Karmarkar-Karp's 2^{-O(log^2 m)} guarantee is nearly optimal for NPP. The reductions are carefully structured, follow the Micciancio-Regev framework, and are versatile with respect to the input distribution and the solution set. The NPP reduction's use of the Chinese remainder theorem to compress n-dimensional lattice information into a one-dimensional NPP instance is elegant. The main theorems are stated with explicit parameters, and the polynomial-hardness SBP result and the NPP result are essentially sound. The near-optimal SBP claim in Remark 1, however, is not supported by the written proof, as detailed below.","major_comments":[{"comment":"The near-optimal SBP claim is not established by the written proof. In the proof of Theorem 3, Proposition 1 and the invocation of Lemma 8 give a total statistical distance of O(m e^{-ln^2 n}) between the matrix fed to the SBP oracle and the Gaussian ensemble N(0,1)^{n×m}. This is negligible in the main body of Theorem 3 because there m=n^{Θ(1/ε)} is polynomial in n. Remark 1, however, sets m=2^{O(n^{3/(2c)})}. For any fixed c>3, this m is super-polynomial in n and, since n^{3/(2c)} grows faster than ln^2 n, the product m e^{-ln^2 n}=exp(Θ(n^{3/(2c)})-Θ(ln^2 n)) diverges. Hence the reduction does not produce an input statistically close to the Gaussian distribution on which the SBP solver is assumed to succeed, and the claimed hardness for κ(x)=1/(√x log^{1+c} x) does not follow as written. A likely repair is to base the smoothing parameter and error on m rather than n: set σ2=ln m, γ=4m ln m, and use smoothing error e^{-ln^2 m}; then the total error becomes m e^{-ln^2 m}=negl(m), the approximation factor remains 2^{O(n^{3/(2c)})}, and the norm bound becomes (ln m)^c ≥ 8n^{3/2}, which is consistent with m=2^{O(n^{3/(2c)})}. The authors should either incorporate this parameter change or restrict the near-optimal claim accordingly.","section":"§3.1, Remark 1"}],"minor_comments":[{"comment":"The displayed statistical closeness bound for W states Δ(W, N(0, σ2^2/2)^{n×m}) ≤ ..., but Lemma 8 gives variance σ^2 for D_{Z^n+v, σ√(2π)}, so the correct covariance is σ2^2 I_n per column, not σ2^2/2. With the printed covariance, A=W/σ2 would be close to N(0,1/2), not N(0,1). This is a typo, but it should be corrected since the subsequent scaling argument relies on the σ2^2 variance.","section":"§3.1, Theorem 3 proof"},{"comment":"The sentence 'By closure, we know e'' ∈ 1/q·Z/qZ' is imprecise, because f is sampled continuously from [0,1/q)^m, so e''=f^T x+e' is not automatically in the discrete set 1/q·Z/qZ. The intended argument is that e'' is small and satisfies e'' ≡ -φ(⌊A⌋_p x) (mod 1), which forces equality with the unique small representative in 1/q·Z/qZ. This should be stated explicitly.","section":"§4, Theorem 4 proof"},{"comment":"The passage from hardness for κ(m)=2^{-log^{2+ε} m} to hardness for κ(m)=2^{-log^{3+ε} m} for arbitrary ε>0 requires instantiating Theorem 4 with parameter 1+ε rather than with the same ε. With the same ε and ε<1, the resulting lattice algorithm runs in time 2^{O(n^{1/(1+ε)})}, which is not ruled out by Assumption 2. The text should spell out this parameter shift.","section":"§4, Corollary 3"},{"comment":"The lower bound on the number of primes in [N,10N] is derived as π(10N)-π(N) > 4N/ln N - 2N/ln N = 2N/ln N, which is indeed at least N/ln N. The text says only that π(10N)>4N/ln N and then 'by taking the difference'; adding the explicit subtraction would avoid confusion.","section":"§4, proof of Lemma 14"}],"recommendation":"major_revision","confidential_remarks":"The main theorems of the paper are carefully argued and the polynomial-hardness SBP and NPP results appear sound. The near-optimal SBP claim in Remark 1 is the one load-bearing point that needs repair; the suggested parameter change appears viable and within the scope of the paper, so I do not recommend rejection. The manuscript would also benefit from clarifying the parameter shift in Corollary 3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper is a clean worst-case-to-average-case reduction from approximate lattice problems to symmetric binary perceptrons and number partitioning. That is a genuine step: it is the first time these average-case problems are shown hard at the algorithmic thresholds under a standard lattice assumption, and it confirms the GKPX22 conjecture up to log factors while showing Karmarkar–Karp is nearly tight. The reduction carefully follows the Micciancio–Regev smoothing framework, and the CRT trick for NPP is a nice touch. The versatility (uniform matrices, zero entries, larger alphabet) is a real plus. The main results deserve a serious referee.\n\nThat said, the near-optimal SBP statement in Remark 1 is not proven as written. The proof of Theorem 3 sets \\sigma_2 = \\ln n and uses \\epsilon = e^{-\\ln^2 n} for the smoothing error. For the polynomial-hardness regime (m = n^{\\Theta(1/\\epsilon)}), the total distance m e^{-\\ln^2 n} is negligible, so that part is fine. But in the near-optimal regime the paper sets m = 2^{O(n^{3/(2c)})}, which is super-polynomial in n; then m e^{-\\ln^2 n} diverges and the input A fed to the SBP solver is not statistically close to the Gaussian distribution on which the solver is assumed to succeed. This is a load-bearing gap for the near-optimal theorem. The likely fix is to switch to \\gamma = 4m\\ln m and smoothing error e^{-\\ln^2 m}, and to enlarge the constant in the exponent of m so the norm bound still goes through with \\sigma_2 = \\ln m. That seems plausible, but it needs to be written out and checked.\n\nMinor issues: there is a covariance-scale typo in the proof of Theorem 3 (the continuous Gaussian should have covariance \\sigma_2^2 I, not \\sigma_2^2/2, if Lemma 8 is being applied correctly), and Lemma 8 is only sketched, leaning on GVV22 and MR07. None of these affect the polynomial SBP theorem or the NPP theorem. The assumptions are the standard subexponential hardness of lattice problems; they are clearly stated and properly attributed. The citation pattern is fine: the main reductions rely on independent prior work, and self-citations appear in supporting lemmas only.\n\nBottom line: this is a strong paper with one unproven claim in the near-optimal regime. I would send it to peer review, and would tell the authors to fix Remark 1 and clean up the typos. If the near-optimal statement is important to them, they should prove the repaired version explicitly.","headline":"The main SBP and NPP hardness theorems are credible and mostly check out, but the near-optimal SBP claim in Remark 1 has a real parameter bug that makes its proof fail as written; it needs a fix before the paper is accepted.","tokens_in":26345,"tokens_out":5364,"would_cite":true,"duration_ms":43888,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","11H06","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, assuming worst-case lattice problems are hard, the symmetric binary perceptron and random number partitioning have no polynomial-time algorithms at the conjectured parameter ranges.","keywords":["symmetric binary perceptron","number partitioning","average-case hardness","worst-case to average-case reductions","lattice problems","Gaussian smoothing","Chinese remainder theorem","Karmarkar–Karp algorithm"],"falsifier":"The reduction is constructive, so a direct test is possible: take a family of worst-case lattice bases with known geometry, run the smoothing construction to produce random SBP or NPP instances, and apply a candidate polynomial-time solver. If the solver succeeds with non-negligible probability on instances generated from every basis, the reconstruction step outputs a lattice point within distance $r+\\|\\mathbf{S}\\|/8$ of the target, solving IncGDD$_\\gamma$ and hence SIVP/GapCRP/GDD; exhibiting such a solver on the constructed distribution would refute Assumptions 1 and 2. A simpler falsifier is a polynomial-time algorithm achieving $\\kappa(m)=2^{-\\omega(\\log^2 m)}$ on random number-partitioning instances, which would improve on Karmarkar–Karp and contradict the NPP corollary.","tokens_in":25259,"feed_emoji":"🧮","tokens_out":19423,"duration_ms":160234,"temperature":0.7,"pith_summary":"This paper tries to prove that two average-case search problems—the symmetric binary perceptron (find a $\\{\\pm1\\}$ vector whose product with a random Gaussian matrix has small $\\ell_\\infty$ norm) and random number partitioning (split random numbers into two groups with sums as close as possible)—are computationally hard, conditional on the worst-case hardness of standard lattice problems. If the paper is right, it confirms up to lower-order terms the conjecture that the best known polynomial-time perceptron guarantee, $\\kappa(x)=\\Theta(1/\\sqrt{x})$, cannot be pushed substantially further, and it shows that the classical Karmarkar–Karp differencing algorithm for number partitioning is nearly optimal. The proof works by smoothing: Gaussian noise turns a worst-case lattice basis into a nearly uniform random instance, and any solver for the random instance is then lifted back to a short lattice vector. The relevance is that these problems exhibit a wide statistical-computational gap, and this gives a worst-case-to-average-case explanation of that gap.","feed_headline":"Lattice hardness implies perceptron and number partitioning are hard","feed_subtitle":"A reduction from worst-case lattice problems proves, under standard hardness assumptions, both random problems are hard to solve on average.","key_machinery":"The carrying mechanism is Gaussian smoothing: for an $n$-dimensional lattice $\\Lambda$, if a Gaussian's width exceeds the smoothing parameter $\\eta_\\varepsilon(\\Lambda)$, its reduction modulo $\\Lambda$ is statistically close to uniform. The reductions sample $\\mathbf{U}$ from a Gaussian of width $\\sigma_1 = r/(4m)$, add uniform lattice vectors $\\mathbf{V}$, and form $\\tilde{\\mathbf{A}} = \\mathbf{S}^{-1}(\\mathbf{V}+\\mathbf{U}) \\bmod \\mathbb{Z}^n$, which is nearly uniform on $[0,1)^{n\\times m}$ while encoding the worst-case basis. A solution $\\mathbf{A}\\mathbf{x}+\\mathbf{e}=\\mathbf{0}$ with $\\|\\mathbf{e}\\|_\\infty \\le \\kappa(m/n)\\sqrt{m}$ is scaled up and lifted to $\\mathbf{s}=x_1(\\mathbf{U}\\mathbf{x}+\\mathbf{S}\\mathbf{e}')\\in \\Lambda(\\mathbf{B})$ with $\\|\\mathbf{s}-\\mathbf{t}\\|_2 \\le r + \\|\\mathbf{S}\\|/8$, exactly the IncGDD guarantee. For number partitioning, a normalized Chinese-remainder isomorphism $\\tilde\\varphi:\\bigoplus_i (1/p_i)\\mathbb{Z}/p_i\\mathbb{Z}\\to (1/q)\\mathbb{Z}/q\\mathbb{Z}$ with $q=\\prod_i p_i$ converts the vector congruence into a scalar inner product $\\mathbf{a}^\\top\\mathbf{x}$; choosing $p_i\\ge 32nm$ and bounding the accumulated error by $2m/q$ prevents wraparound when inverting $\\tilde\\varphi$.","core_discovery":"On its own terms, the paper establishes two conditional average-case hardness theorems. Theorem 3 reduces the worst-case lattice problem IncGDD (incremental guaranteed distance decoding: given a lattice basis, $n$ short independent lattice vectors, a target, and a radius, find a lattice point within $r+\\|\\mathbf{S}\\|/8$ of the target) with approximation factor $\\gamma(n)=n^{O(1/\\varepsilon)}$ to SBP with $\\kappa(x)=1/x^{1/2+\\varepsilon}$. Since the worst-case problems GDD (guaranteed distance decoding), SIVP (shortest independent vectors), and GapCRP (gap covering radius) all reduce to IncGDD, Corollary 2 follows: under Assumption 1 (polynomial hardness of those problems), no polynomial-time algorithm solves average-case SBP at that $\\kappa$; under the stronger subexponential Assumption 2, a variant yields hardness for $\\kappa(x)=1/(\\sqrt{x}\\,\\log^c x)$ for a sufficiently large constant $c$. Theorem 4 performs the same reduction in dimension $n=\\Omega((\\log m)^{1+\\varepsilon})$ to NPP at $\\kappa(m)=2^{-\\log^{2+\\varepsilon} m}$, and composing with Assumption 2 gives Corollary 3: no polynomial-time algorithm solves NPP at $\\kappa(m)=2^{-\\log^{3+\\varepsilon} m}$. The paper therefore claims to prove the GKPX22 conjecture up to lower-order terms and to show that the Karmarkar–Karp differencing algorithm is nearly tight, all conditional on worst-case lattice hardness.","pith_inferences":["Beyond the paper: if the requirement $m\\gg n^{\\Theta(1/\\varepsilon)}$ could be relaxed to $m=\\Theta(n)$, the proof would directly abut the statistical threshold $\\kappa_{\\mathrm{stat}}(x)=2^{-\\Theta(x)}$ and would determine whether the computational-statistical gap persists at constant aspect ratio; the current reduction breaks in that regime.","Beyond the paper: the smoothing-to-average-case template may transfer to the asymmetric binary perceptron, since the difficulty there is again finding a sign vector with small linear image; the authors explicitly leave this as an open question.","Beyond the paper: the CRT embedding suggests that other scalar-output average-case problems, such as random subset-sum or one-dimensional SIS with a composite modulus, could inherit near-tight worst-case lattice hardness from the same no-wraparound argument."],"forward_implications":["If any of the worst-case lattice problems SIVP, GapCRP, or GDD with $\\gamma(n)=n^{O(1/\\varepsilon)}$ requires super-polynomial time, then no polynomial-time algorithm solves average-case SBP with $\\kappa(x)=1/x^{1/2+\\varepsilon}$, even with inverse-polynomial success probability.","If Assumption 2 holds, then no polynomial-time algorithm solves SBP with $\\kappa(x)=1/(\\sqrt{x}\\log^c x)$ for a sufficiently large constant $c$, and none solves NPP with $\\kappa(m)=2^{-\\log^{3+\\varepsilon} m}$.","The Karmarkar–Karp guarantee $2^{-O(\\log^2 m)}$ for number partitioning is optimal up to one logarithmic factor in the exponent, and the GKPX22 conjecture for the perceptron is confirmed up to lower-order terms.","The hardness statement is robust: it survives under uniform $[0,1]$ input distributions, under weaker solution requirements $\\mathbf{x}\\in\\{-1,0,1\\}^m\\setminus\\{\\mathbf{0}\\}$, and when the solver need only succeed with non-negligible probability."],"supporting_citations":[{"why":"Supplies the Gaussian-smoothing lemmas, defines IncGDD, and gives the reductions from SIVP, GapCRP, and GDD to IncGDD that the proofs compose.","marker":"[MR07]"},{"why":"States the conjecture that the efficient SBP guarantee is $\\tilde{\\Theta}(1/\\sqrt{x})$, which the paper proves up to lower-order terms.","marker":"[GKPX22]"},{"why":"Establishes the best known polynomial-time SBP guarantee $\\Theta(1/\\sqrt{x})$ that the hardness result declares essentially optimal.","marker":"[BS20]"},{"why":"Introduces the differencing algorithm whose $2^{-O(\\log^2 m)}$ number-partitioning guarantee is shown to be nearly tight.","marker":"[KK82]"},{"why":"Proves the Karmarkar–Karp guarantee $2^{-O(\\log^2 m)}$, fixing the algorithmic baseline for the NPP hardness result.","marker":"[Yak96]"},{"why":"Shows statistically that NPP solutions exist with $\\kappa(m)=\\Theta(2^{-m})$, defining the statistical side of the gap.","marker":"[KKLO86]"},{"why":"Establishes the statistical threshold for SBP solutions, delineating the computational-statistical gap the hardness result targets.","marker":"[APZ19]"}],"fun_headline_variants":["Lattice hardness implies perceptron and partition hardness","Assuming lattice hardness, perceptron and partitioning are hard","Worst-case lattice hardness makes partitioning and perceptron hard","Perceptron and number partitioning hard under lattice assumption"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that approximate worst-case lattice problems (SIVP, GapCRP, GDD) are genuinely hard—in the strong versions, require $2^{\\omega(n^{1/2-\\varepsilon})}$ time even with approximation factor $2^{n^{1/2-\\varepsilon}}$—so any future improvement in lattice reduction beyond the known time-versus-approximation tradeoff would weaken or invalidate the hardness conclusions.","fun_headline_variants_meta":{"raw":{"variants":["Lattice hardness implies perceptron and partition hardness","Assuming lattice hardness, perceptron and partitioning are hard","Worst-case lattice hardness makes partitioning and perceptron hard","Perceptron and number partitioning hard under lattice assumption"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00121,"raw_usage":{"total_tokens":5163,"prompt_tokens":1307,"completion_tokens":3856,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":923,"completion_tokens_details":{"reasoning_tokens":3793}},"tokens_in":923,"tokens_out":3856,"duration_ms":26687,"temperature":1.0,"reasoning_tokens":3793,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T12:43:45.450928+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The reduction is constructive, so a direct test is possible: take a family of worst-case lattice bases with known geometry, run the smoothing construction to produce random SBP or NPP instances, and apply a candidate polynomial-time solver. If the solver succeeds with non-negligible probability on instances generated from every basis, the reconstruction step outputs a lattice point within distance $r+\\|\\mathbf{S}\\|/8$ of the target, solving IncGDD$_\\gamma$ and hence SIVP/GapCRP/GDD; exhibiting such a solver on the constructed distribution would refute Assumptions 1 and 2. A simpler falsifier is a polynomial-time algorithm achieving $\\kappa(m)=2^{-\\omega(\\log^2 m)}$ on random number-partitioning instances, which would improve on Karmarkar–Karp and contradict the NPP corollary.","supporting_citations":[],"review_version":1}