Pith. sign in

REVIEW 3 major objections 5 minor 29 references

Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem

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

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

Pith's one-line read The paper establishes a deterministic algebraic algorithm for the $(n,k)$-complete hidden subset sum problem: from the multiset of all $k$-subset sums it recovers the hidden multiset $X$ as the roots of a degree-$n$ polynomial, whenever a…

desk verdict Solid symmetric-polynomial algorithm for the (n,k)-complete HSSP, but Algorithm 2's pseudocode has inverted conditions and the exact-real assumption is unaddressed. read the letter →

arxiv 2412.04967 v2 pith:K7XSM62P submitted 2024-12-06 math.CO math.NT

Lixia Luo , Changheng Li , Qiongxiu Li This is my paper · ORCID
classification math.COmath.NT MSC 05E0505A1711P8111B73
keywords hiddensubsetsumproblemmultisetrecoverysymmetricpolynomialspowersumselementaryintegerpartitionsdeterministicalgorithmsingularparameterpairs
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

The paper proposes two deterministic algorithms for the $(n,k)$-complete hidden subset sum problem, in which one must recover a multiset $X$ of $n$ real numbers from the multiset of all $\binom{n}{k}$ sums of $k$ distinct elements. One is an ordering-pruned brute-force search; the other is an algebraic recovery method. The algebraic method converts the subset-sum data into power sums $S_u$ of the given sums, solves a sequence of square linear systems whose unknowns are symmetric polynomials of $X$ indexed by integer partitions of $u$, and obtains the elementary symmetric polynomials $e_1,\dots,e_n$. From those it builds the degree-$n$ polynomial $x^n-e_1x^{n-1}+\cdots+(-1)^n e_n$, whose roots are exactly the hidden elements. The recovery is guaranteed whenever a certain determinant is nonzero for every $u=1,\dots,n$; the paper computes that determinant in closed form and shows that its vanishing is the condition previously known to control the uniqueness of solutions. If the condition holds, the deterministic runtime is $O\!\big(\sum_{u=1}^n p(u,\le k)^3+\binom{n}{k}n\big)$, where $p(u,\le k)$ counts partitions of $u$ into at most $k$ parts.

What carries the argument

The key object is a square matrix (Matrix (1) in the paper) whose rows and columns are labelled by partitions of $u$ into at most $k$ parts. Its first row records the coefficients that express the $u$-th power sum $S_u$ of the subset-sum data in terms of the partition-indexed symmetric polynomials of $X$; the other rows record coefficients that express products of lower-degree power sums in the same basis. Invertibility of this matrix for every $u=1,\dots,n$ is what lets the algorithm determine all elementary symmetric polynomials of $X$. The second ingredient is the coefficient–root relation: a monic degree-$n$ polynomial is fixed by its elementary symmetric coefficients, and its roots are precisely the elements of $X$. The paper derives the determinant of Matrix (1) in closed form and uses it to identify the $(n,k,u)$ combinations where the linear system collapses.

What would settle it

Run the paper's symmetric subset sum recovery algorithm on a small non-singular instance with known data, for example $X=\{1,2,3,4,5\}$ with $k=2$, in the paper's exact-arithmetic model on the ten pairwise sums; if the output multiset differs from $X$, the recovery claim is false. Separately, compute Matrix (1) for a small pair such as $n=5,k=2,u=3$ and compare its numerical determinant with $\sum_{i=1}^u(-1)^{i-1}(i-1)!\,S(u,i)\binom{n-i}{k-i}$; any mismatch would falsify the closed-form determinant theorem.

Watch

Extended reading notes

Core claim

The central discovery is that the entire algebraic content of the $(n,k)$-complete HSSP can be organized as a sequence of square linear systems. For each degree $u$, the $u$-th power sum $S_u$ of all $k$-subset sums is a linear combination of the symmetric polynomials indexed by partitions of $u$, with binomial and multinomial coefficients; products of lower-degree power sums supply the remaining rows of the coefficient matrix. The paper proves that this matrix is invertible exactly when $\sum_{i=1}^u (-1)^{i-1}(i-1)!\,S(u,i)\binom{n-i}{k-i}\neq 0$, equivalently $\sum_{j=1}^k (-1)^{j-1}j^{u-1}\binom{n}{k-j}\neq 0$. When this holds for every $u$, the elementary symmetric polynomials are uniquely determined, standard power-sum identities fill in the higher ones, and the hidden multiset is recovered as the roots of the polynomial built from those coefficients. The paper also proves that if the first failure occurs at degree $u_0$, no basis for the degree-$u$ homogeneous symmetric polynomial ring with $u\ge u_0$ can be constructed from the available subset-sum power sums, so the obstruction is intrinsic to the data.

Load-bearing premise

The deterministic guarantee assumes an idealized exact-arithmetic model in which power sums, matrix inversions, and the roots of the degree-$n$ polynomial are computed exactly; the paper gives no error analysis for the numerical root-finding step, so the guarantee need not survive floating-point rounding.

Editorial extensions

If this is right

  • On every instance that satisfies the nonzero-determinant condition for $u=1,\dots,n$, the hidden multiset is recovered in deterministic worst-case time $O\!\big(\sum_{u=1}^n p(u,\le k)^3+\binom{n}{k}n\big)$, with no random choices and no lattice assumptions.
  • The determinant condition is the same polynomial that the classical uniqueness theory uses; when it vanishes, the classical sufficient condition for uniqueness no longer applies and the algorithm's linear systems collapse.
  • For fixed $k$, the determinant is a degree-$(k-1)$ polynomial in $n$, so the singular values of $n$ are constrained by divisibility: any such $n$ must divide $(k-1)!\,k^{u-1}$; for $k=2$ the only failures occur at $n=2^{u-1}$.
  • If the first singular degree is $u_0$, then no basis of the degree-$u$ symmetric polynomial ring for $u\ge u_0$ can be constructed from the subset-sum power sums alone, so unique recovery is impossible from that data without extra information.
  • The algebraic recovery method transfers to any field or ring in which $n!$ and each determinant value are invertible and the coefficient–root relations hold, provided the arithmetic is exact.

Reading between the lines

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

  • Read as a complexity statement, the bound implies polynomial time for every fixed $k$: since $p(u,\le k)=O(u^{k-1})$, the summed term is polynomial in $n$, so the algebraic method is an explicit polynomial-time deterministic route on all non-singular instances with $k$ fixed.
  • Because the determinant has a closed form, an implementation can check all $u=1,\dots,n$ symbolically before solving any linear system, turning the singularity condition into a certificate that either guarantees recovery or identifies the first failing degree.
  • The method invites stress-testing on partial or noisy versions of the problem, such as recovering $X$ from a proper subset of the $k$-subset sums; Theorem 4 rules out symmetric subsets that carry full information, but it leaves asymmetric partial samples unexplored.
  • The tight link between the determinant and the classical uniqueness condition suggests using the algorithm as a constructive uniqueness witness: on non-singular pairs it not only shows that a solution exists but exhibits it.
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 (n,k)-complete Hidden Subset Sum Problem over the reals and proposes two deterministic algorithms. Algorithm 1 is an optimized brute-force search exploiting ordering relations among subset sums. Algorithm 2 is the main contribution: it computes power sums of the hidden multiset X from power sums of the multiset of all k-subset sums through a sequence of linear systems (Matrix (1)), derives the determinant of these systems as a Moser-type polynomial, uses Newton identities to obtain elementary symmetric polynomials, and then recovers X as the roots of the polynomial constructed via Vieta's formulas. The claimed complexity is O(sum_{u=1}^n p(u,<=k)^3 + C(n,k)n). The paper also contains a theorem on permutation-symmetric subsets of X_{n,k} and a discussion of homogeneous symmetric polynomial rings.

Significance. The algebraic core of the paper is attractive and largely self-contained: the recursive extraction of power sums from subset sums is a natural application of symmetric function theory, the determinant formula is identified with the classical Moser polynomials, and the algorithm has no fitted parameters or circular normalizations. If Theorem 2 is made fully rigorous under a well-defined real computation model, the result would be a genuinely deterministic algebraic recovery method whose complexity is substantially better than exhaustive search for small k and moderate n. The discussion of when a basis of the homogeneous symmetric polynomial ring can be constructed from the subset-sum power sums S_u is also of independent interest. However, as printed, the central algorithmic claim is undermined by concrete pseudocode errors and by the lack of an exact model for the root-finding step.

major comments (3)
  1. [§4.4, Algorithm 2] The pseudocode contradicts Theorem 2. Line 13 reads "if k > n(L[j]) then break", but L[1] = (u) has length 1 and k >= 2, so the loop over j breaks immediately and the first row of M remains all zeros, making M singular on every input. The surrounding text and the matrix formula show that the intended condition is the opposite, namely n(L[j]) > k (or no break at all, since L already contains only partitions into at most k parts). Line 3 reads "if sum ... then return failure", which in standard pseudocode returns failure exactly when the determinant is nonzero, i.e. exactly when Theorem 2 guarantees recovery; the intended condition is "if sum ... == 0". These two errors make Algorithm 2 non-executable as printed and mean the current proof of Theorem 2 does not establish the stated deterministic recovery claim.
  2. [§4.4, line 32 and Theorem 2] The exact deterministic guarantee is not supported for the root-finding step. The instruction "Find the n roots of the polynomial" is not a finite exact operation in the standard BSS model over R, and the cited O(n^3) method based on companion-matrix eigenvalues is numerical. To substantiate Theorem 2 as stated, the paper needs to specify the real computation model, for example by treating roots as an oracle and counting that oracle as a unit-cost operation, or by giving an exact real-algebraic root isolation procedure with an appropriate complexity bound and error analysis. As written, the claimed deterministic recovery and the stated O(n^3) term for root finding are not justified.
  3. [§4.3, proof of Theorem 3] The proof of the determinant formula is too compressed at the point where the null vector c is related to the cofactors d_{i,j}. After Equation (2), the statement "Since d_{1,1}=1=c_{1,1}, it follows that d_{i,j}=c_i" needs the explicit chain: if B is the submatrix of Matrix (1) obtained by deleting the first row, then Bc=0 with c_1=1 gives B'(c_2,...,c_m) = -b_1, where B' is B with its first column b_1 removed; Lemma 2 then identifies (c_2,...,c_m) with the ratios of first-row cofactors A_{1j}/A_{11}. This link is not stated, and the current text jumps from a null-space computation to the cofactor expansion. Because the determinant formula is the invertibility criterion on which Theorem 2 rests, the proof should be expanded and the roles of c, b_1, and B' made explicit.
minor comments (5)
  1. [§4.4, line 1] The condition "if n|(k-1)!kn" is ambiguous; it should state explicitly whether the exponent is n-1 or n, e.g. "if n divides (k-1)! k^{n-1}".
  2. [Remark 2] "Morse polynomial" should be "Moser polynomial".
  3. [§4.6] The answer to Question 1 is given as "No with high probability!"; this informal phrasing should be replaced by a precise conjecture or by a theorem with a proof, since the surrounding discussion is otherwise rigorous in tone.
  4. [§4.4, bottom paragraph] The sentence "no closed-form expression for the partition function is known" is inaccurate: exact formulas are known (for instance, the Hardy-Ramanujan-Rademacher series). The intended statement is presumably that no simple polynomial-type closed form exists.
  5. [§3, Algorithm 1] The counter-update logic in lines 23-36 is intricate and would benefit from a short invariant or example, because as presented it is hard to verify that all index combinations are generated exactly once.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the recovery algorithm is self-contained algebra, with the invertibility condition checked independently from n and k rather than fitted to the data.

full rationale

All load-bearing derivation steps in this paper are self-contained algebraic identities rather than fits, self-citations, or renamed predictions. Theorem 2's symmetric subset sum recovery algorithm computes the partition-indexed power sums P_p by solving the linear system Matrix (1), obtains the elementary symmetric polynomials via Newton's identities, and then constructs the degree-n polynomial whose roots are exactly the hidden multiset X via Vieta's formulas. The success condition is the nonvanishing of the determinant sum_{i=1}^u (-1)^{i-1}(i-1)!S(u,i) binom(n-i,k-i), and Section 4.3 proves this determinant is equal to the classical Moser polynomial; the condition therefore depends only on n and k, not on the input multiset X_{n,k} or on the output X. No parameter is fitted to a subset of the data and then reported as a prediction; the algorithm consumes the full subset-sum multiset and directly produces the hidden multiset. The cited uniqueness facts in [6] and [10] are external to this paper and are not used to justify the algorithm's correctness; correctness follows from the explicit matrix equations, Newton's identities, and Vieta's formulas. The authors' own earlier work [3,4] appears only in the applications and related-work discussion and is not load-bearing for the main theorems. The observation that the determinant equals the Moser polynomial is re-derived in Remark 1 and is an external consistency check rather than a circular renaming. Theorem 5 is essentially a restatement of invertibility of Matrix (1), but it is presented as a separate structural discussion and the main recovery algorithm does not depend on it. The pseudocode defects noted in Section 4.4, such as the inverted 'if' conditions, and the idealization of exact root-finding are correctness or numerical-modeling concerns, not circularity.

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

The central claim rests on standard algebraic facts and on the full-input assumption of the problem definition. No free parameters are fitted to data, and no new mathematical objects are postulated. The main domain-specific load is the exact-real arithmetic model and the complete multiset input.

assumptions (4)
  • domain assumption The input X_{n,k} is exactly the complete multiset of all k-subset sums, with no missing, duplicate, or noisy entries.
    The (n,k)-complete HSSP is defined this way in Section 1, and both algorithms rely on having all C(n,k) subset sums.
  • domain assumption Arithmetic over R is exact and unit-cost, including matrix inversion and polynomial root finding.
    The complexity analysis in Section 4.4 counts real operations, and Algorithm 2 line 32 invokes root finding over R.
  • standard math Newton's identities and Vieta's formulas hold over R.
    These are used in Section 4.2.4 to pass from power sums to elementary symmetric polynomials and to construct the target polynomial.
  • standard math The homogeneous symmetric polynomial ring R_u has a basis indexed by partitions of u, and the listed product power sums span the relevant space.
    Used in Section 4.3 and Theorem 5 to analyze Matrix (1) and the determinant condition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem." pith.science (2026). https://pith.science/paper/K7XSM62P

@misc{pith2026241204967,
  author       = {Pith},
  title        = {Pith review of: Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K7XSM62P}},
  note         = {Machine review of arXiv:2412.04967}
}
abstract

The Hidden Subset Sum Problem (HSSP) is a significant NP-complete problem in number theory and combinatorics, with applications in cryptography and AI privacy. For the $(n,k)$-complete HSSP, where a target multiset must be recovered from its all $k$-subset sums, existing algorithms face limitations due to high complexity or intractability. This paper proposes two deterministic algorithms: a brute-force approach, and a novel method leveraging symmetric polynomials and Vieta's formulas with $O\left(\sum_{u=1}^n p(u,\leq k)^3+\binom{n}{k}n\right)$ complexity, where $ p(u,\leq k)$ counts the number of partitions of a positive integer $u$ into at most $k$ parts. The latter constructs an $n$-th degree polynomial via Vieta's formulas, whose roots correspond to the hidden multiset elements. Additionally, the discussion about the homogeneous symmetric polynomial rings is of independent interest.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Speeding up discrete log and factoring based schemes via precomputat ions

    Victor Boyko, Marcus Peinado, and Ramarathnam Venkates an. Speeding up discrete log and factoring based schemes via precomputat ions. In Inter- national Conference on the Theory and Applications of Cryptogr aphic Tech- niques, pages 221–235. Springer, 1998

    work page 1998

  2. [2]

    Nonneg- ative integral subset representations of integer sets

    Michael J Collins, David Kempe, Jared Saia, and Maxwell Y oung. Nonneg- ative integral subset representations of integer sets. Information Processing Letters, 101(3):129–133, 2007

    work page 2007

  3. [3]

    On the privacy of federated clu stering: A cryp- tographic view

    Qiongxiu Li and Lixia Luo. On the privacy of federated clu stering: A cryp- tographic view. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages 4865–4869. IEEE, 2024

    work page 2024

  4. [4]

    Perfect Gradient Inversion in Federated Learning: A New Paradigm from the Hidden Subset Sum Problem

    Qiongxiu Li, Lixia Luo, Agnese Gini, Changlong Ji, Zhanh ao Hu, Xiao Li, Chengfang Fang, Jie Shi, and Xiaolin Hu. Perfect gradient in version in feder- ated learning: A new paradigm from the hidden subset sum prob lem. arXiv preprint arXiv:2409.14260, 2024

    work page Pith review arXiv 2024

  5. [5]

    Chan nel allocation revisited through 1-extendability of graphs

    Anthony Busson, Malory Marin, and R´ emi Watrigant. Chan nel allocation revisited through 1-extendability of graphs. In International Symposium on Algorithmics of Wireless Networks , pages 46–60. Springer, 2024

    work page 2024

  6. [6]

    Is the multiset of n integers uniquely det ermined by the multiset of its s-sums? The American Mathematical Monthly , 126(5):400– 417, 2019

    Dmitri V Fomin. Is the multiset of n integers uniquely det ermined by the multiset of its s-sums? The American Mathematical Monthly , 126(5):400– 417, 2019. 24

    work page 2019

  7. [7]

    Multiset theory

    Wayne D Blizard. Multiset theory. Notre Dame Journal of formal logic , 30(1):36–66, 1989

    work page 1989

  8. [8]

    Leo Moser. E1248. The American Mathematical Monthly , 64(7):507–507, 1957

    work page 1957

Show all 29 references
  1. [9]

    Unsolved problems in number theory, volume 1

    Richard Guy. Unsolved problems in number theory, volume 1. Springer Science & Business Media, 2004

    2004

  2. [10]

    On the determinatio n of numbers by their sums of a fixed order

    John L Selfridge and Ernst G Straus. On the determinatio n of numbers by their sums of a fixed order. Pacific J. Math. , 8(4):847–856, 1958

    1958

  3. [11]

    On the determination of sets by the sets of sums of a certain order

    Basil Gordon, Aviezri S Fraenkel, and Ernst G Straus. On the determination of sets by the sets of sums of a certain order. Pacific J. Math , 12(19621):187– 196, 1962

    1962

  4. [12]

    On the determination of sets by sets of sums of fixed order

    John A Ewell. On the determination of sets by sets of sums of fixed order. Canadian Journal of Mathematics , 20:596–611, 1968

    1968

  5. [13]

    Collections of mult iple sums

    Dmitri V Fomin and Oleg T Izhboldin. Collections of mult iple sums. Trans- lations of the American Mathematical Society-Series 2 , 166:201–214, 1995

    1995

  6. [14]

    Examples of non-uniquen ess for the com- binatorial radon transform modulo the symmetric group

    Jan Boman and Svante Linusson. Examples of non-uniquen ess for the com- binatorial radon transform modulo the symmetric group. Mathematica Scan- dinavica, pages 207–212, 1996

    1996

  7. [15]

    A set of 12 n umbers is not determined by the set of its 4-sums

    Javlon E Isomurodov and Konstantin P Kokhas. A set of 12 n umbers is not determined by the set of its 4-sums. Journal of Mathematical Sciences , 224:258–262, 2017

    2017

  8. [16]

    On the determina tion of sets by their subset sums

    Andrea Ciprietti and Federico Glaudo. On the determina tion of sets by their subset sums. arXiv preprint arXiv:2301.04635 , 2023

    2023 arXiv

  9. [17]

    A genetic algorithm for the minimum generating set problem

    Manuel Lozano, Manuel Laguna, Rafael Mart ´ ı, Francisc o J Rodr ´ ıguez, and Carlos Garc ´ ıa-Mart ´ ınez. A genetic algorithm for the minimum generating set problem. Applied Soft Computing , 48:254–264, 2016

    2016

  10. [18]

    The hardness of the hidd en subset sum problem and its cryptographic implications

    Phong Nguyen and Jacques Stern. The hardness of the hidd en subset sum problem and its cryptographic implications. In Advances in Cryptol- ogy—CRYPTO’99: 19th Annual International Cryptology Conferenc e Santa Barbara, California, USA, August 15–19, 1999 Proceedings 19 , pages ...

    1999

  11. [19]

    A polynomial-t ime algorithm for solving the hidden subset sum problem

    Jean-S´ ebastien Coron and Agnese Gini. A polynomial-t ime algorithm for solving the hidden subset sum problem. In Annual International Cryptology Conference, pages 3–31. Springer, 2020

    2020

  12. [20]

    Provably solvi ng the hidden subset sum problem via statistical learning

    Jean-S´ ebastien Coron and Agnese Gini. Provably solvi ng the hidden subset sum problem via statistical learning. Mathematical Cryptology , 1(2):70–84, 2021

    2021

  13. [21]

    On the hardness of the hidden subset sum problem: algebraic a nd statistical attacks

    Agnese Gini. On the hardness of the hidden subset sum problem: algebraic a nd statistical attacks. PhD thesis, Unilu-University of Luxembourg, Luxembourg, 2022

    2022

  14. [22]

    A comprehensiv e survey of privacy-preserving federated learning: A taxonomy, revie w, and future di- rections

    Xuefei Yin, Yanming Zhu, and Jiankun Hu. A comprehensiv e survey of privacy-preserving federated learning: A taxonomy, revie w, and future di- rections. ACM Computing Surveys (CSUR) , 54(6):1–36, 2021

    2021

  15. [23]

    Algebra, volume 211

    Serge Lang. Algebra, volume 211. Springer Science & Business Media, 2012

    2012

  16. [24]

    Integer partitions

    George E Andrews and Kimmo Eriksson. Integer partitions. Cambridge Uni- versity Press, 2004

    2004

  17. [25]

    Enumerative Combinatorics Volume 1 second edition

    Richard P Stanley. Enumerative Combinatorics Volume 1 second edition . Cambridge studies in advanced mathematics, 2011

    2011

  18. [26]

    Numerical Linear Algebra

    Lloyd N Trefethen and David Bau. Numerical Linear Algebra . Society for Industrial and Applied Mathematics, Philadelphia, PA, 199 7

  19. [27]

    Introduction to algorithms , volume 3

    Charles Eric Leiserson, Ronald L Rivest, Thomas H Corme n, and Clifford Stein. Introduction to algorithms , volume 3. MIT press Cambridge, MA, USA, 1994

    1994

  20. [28]

    Polynomial roots fr om companion matrix eigenvalues

    Alan Edelman and Hiroshi Murakami. Polynomial roots fr om companion matrix eigenvalues. Mathematics of Computation , 64(210):763–776, 1995

    1995

  21. [29]

    Asymptotic fo rmulaæ in combi- natory analysis

    Godfrey H Hardy and Srinivasa Ramanujan. Asymptotic fo rmulaæ in combi- natory analysis. Proceedings of the London Mathematical Society, 2(1):75–115, 1918. 26

    1918

Pith tools

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