Pith. sign in

REVIEW 2 major objections 4 minor 54 references

Improved Quantum Algorithms for Subset Sum and $k$-SUM

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read A single four-block quantum walk beats the previous worst-case k-SUM bound for every k>3, yielding quantum Subset Sum in O^*(2^{2n/7}).

desk verdict Real improvement in quantum k-SUM/Subset Sum with a fixable but load-bearing typo in the main parameter. read the letter →

arxiv 2608.07309 v1 pith:2ITUX3EY submitted 2026-08-07 cs.CC

Nikolai Chukhin , Alexander S. Kulikov , Maksim Levitskii , Ivan Mihajlin This is my paper · ORCID
classification cs.CC MSC 68Q1268Q25
keywords k-SUMSubsetSumquantumwalkJohnsongraphClawFindingrandomprimefilteringmeet-in-the-middle
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

This paper claims a new quantum algorithm for the worst-case k-SUM problem, not just for random instances. The central result is that k-SUM can be solved in quantum time O~($n^{{\Psi_k}}$) for every k>3, where \Psi_k = \Phi_k minus corrections for k congruent to 3 or 6 modulo 7. This improves the previous worst-case quantum bound O~($n^{{k/3}}$) and, asymptotically, the exponent is 2k/7 + O(1). The same machinery applied to the case k=7 gives a quantum Subset Sum algorithm running in O^*($2^{{2n/7}}$), improving the earlier O^*($2^{{n/3}}$). A sympathetic reader should care because this is a concrete advance on two central NP-complete searching problems and transfers the known random-instance speedup to all instances.

What carries the argument

The core mechanism is a quantum walk on the Johnson graph J(X_2,m) \times J(X_4,m): the k input lists are grouped into four consecutive blocks of sizes roughly (3k/14, 2k/7, 3k/14, 2k/7), and the walk searches over m-element samples S_2 and S_4 drawn from the two large block-tuple sets. A random prime p is chosen from [m\$log^{2}$ n, 2m\$log^{2}$ n], and each sampled vertex stores dictionaries of sums grouped by their residues modulo p. To check a vertex, the algorithm uses quantum search over residues q and then Claw Finding on the reduced left- and right-hand lists. The random prime ensures that, with constant probability, a fixed solution's two block sums are exposed in their residue buckets, giving a constant fraction of marked walk vertices.

What would settle it

Construct a family of k-SUM instances where the inputs have bit-length much larger than O(k\log n), say ~$n^{{100}}$, and test whether a random prime in [m\$log^{2}$ n, 2m\$log^{2}$ n] can fail to isolate a solution with probability bounded away from a constant. A concrete counterexample would be a set of sums where a nonzero difference is divisible by many primes in that interval, violating the O(\log|z|/M) bound used in the proof.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for every integer k>3, worst-case k-SUM can be solved in quantum time O~($n^{{\Psi_k}}$), where \Psi_k = (2k - \lfloor k/7 \rfloor - \lfloor (k+3)/7 \rfloor)/6 - [k\equiv 3 \bmod 7]/9 - [k\equiv 6 \bmod 7]/18. This is a worst-case upper bound, improving Tani's O~($n^{{k/3}}$) for every k>3, and it matches or improves the random-instance exponent \Phi_k for all k. A corollary is that the Subset Sum problem can be solved in quantum time O^*($2^{{2n/7}}$), improving the previously known O^*($2^{{n/3}}$). The algorithm also gives a positive answer for the Pigeonhole Modular Equal Subset Sum problem in quantum time O^*($3^{{2n/7}}$).

Load-bearing premise

The load-bearing premise is that a uniformly random prime p in the interval [m\$log^{2}$ n, 2m\$log^{2}$ n] divides any nonzero difference of two relevant sums with probability O(1/(m\log n)), which relies on all input integers having bit-length O(k\log n); if that fails, the constant marked fraction of walk vertices degrades.

Editorial extensions

If this is right

  • For every k>3, the worst-case quantum running time of k-SUM becomes O~(n^{\Psi_k}), strictly below the previous O~(n^{k/3}).
  • Quantum Subset Sum can now be solved in O^*(2^{2n/7}), improving the prior O^*(2^{n/3}).
  • Using k=7 in the block reduction gives O^*(3^{2n/7}) for Pigeonhole Modular Equal Subset Sum.
  • The improvement holds for all worst-case instances with a solution, not only for single-solution random instances.
  • The exponent \Psi_k matches the earlier random-instance exponent \Phi_k for k not congruent to 3 or 6 mod 7, and improves it for k congruent to 3 or 6 mod 7.

Reading between the lines

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

  • The same four-block walk with a random-prime filter may transfer to k-XOR-type problems, where comparable exponents are currently known only for random instances.
  • The residue-class optimization (mod 7) suggests that further tuning, perhaps with other block counts or modulus classes, could shave more off the exponent for specific values of k.
  • Replacing the final Claw Finding step with a faster matching routine might lower the (k_1+k_3)/3 contribution and improve the exponent for small k.
  • If the block-reduction idea extends to more than seven blocks, the quantum exponent for Subset Sum might approach 1/4, though this is not claimed by the paper.
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

2 major / 4 minor

Summary. The paper presents a new quantum algorithm for worst-case k-SUM running in time O~(n^{Psi_k}), where Psi_k = Phi_k - [k≡3 mod 7]/9 - [k≡6 mod 7]/18, improving over Tani's O~(n^{k/3}) for every k>3 and over Schrottenloher's random-instance bound for k≡3,6 mod 7. The algorithm partitions the k lists into four blocks, samples m-element subsets from the two larger blocks, filters by a random prime, and searches with a quantum walk on a product of Johnson graphs, with Claw Finding inside the vertex check. The authors combine the 7-SUM case with the standard block reduction to derive an O*(2^{2n/7}) quantum algorithm for Subset Sum, improving the previous O*(2^{n/3}), and also give an application to Pigeonhole Modular Equal Subset Sum. The proof structure is a correctness proof, a random-prime isolation lemma, and a parameter-balanced runtime analysis, with the final exponents summarized in Table 1.

Significance. If the main theorem is correct after fixing the parameter definition, this is a notable advance: it is the first worst-case quantum k-SUM algorithm to beat Tani's n^{k/3} for all k>3, and it improves the quantum Subset Sum bound from 2^{n/3} to 2^{2n/7}. The exponent Psi_k is derived analytically from the algorithm's own parameters with no fitted constants, and the four-block decomposition with random-prime bucket isolation and a quantum walk on two Johnson graphs is a clean and apparently new alternative to the merging-tree paradigm. The paper also gives a self-contained marked-fraction calculation and a concrete application to a modular pigeonhole variant. However, the current text contains a load-bearing inconsistency in the definition of the sample size m, and the bit-length reduction invoked in Lemma 3.1 is only cited, not stated; both points must be addressed before the proof is verifiable.

major comments (2)
  1. [Section 3.2 / Eq. (1) / Section 3.4 / Algorithm 1] Section 3.2 and Algorithm 1 define m = floor(n^{r/2}), but every subsequent calculation uses m = Theta(n^r). In particular, Eq. (1) asserts |V*|/|V(G)| = m^2/n^{k2+k4} = Omega(n^{2r-k2-k4}), which is valid only when m = Omega(n^r); with m = n^{r/2} the marked fraction would be n^{r-k2-k4}. Likewise, Section 3.4 uses T_set = O~(n^r) and T_chk = O~(n^{(k1+k3)/3+r/2}) from p ~ m log^2 n, both assuming m = n^r. Under the literal definition, for k=7 (r=2, k2=k4=2, ell=3) the total walk time would be O~(n^{2.5}) rather than the claimed O~(n^2), so Theorem 1.2 and Table 1 are not derivable from the text as written. The intended parameter is evidently m = Theta(n^r); the definition should be corrected, for example to m = floor(c n^r) for a constant c<1. If m = n^r is used with r = k2, which occurs in several rows of Table 1, then m = |X_i| and the stated Johnson-graph condition m <= |X|/2 is violated; the corrected definition should also ensure m <= |X_i|/2.
  2. [Section 2.1 / Lemma 3.1] The proof of Lemma 3.1 assumes log|Sigma_i(x) - z*_i| = O(log n), i.e., that all input integers have O(k log n) bits. The only support for this is the one-sentence assertion in Section 2.1 that this can be achieved by 'the standard fingerprinting technique [ALW14]', but no precise statement of the reduction or its error probability is given. A direct modular reduction by a random prime of size n^{O(1)} has a collision probability for a fixed nonzero difference proportional to log|Sigma_i(x)-z*_i| / n^{O(1)}, which is not automatically O(1/(m log n)) if the original integers have large bit-length. The authors should state the exact fingerprinting lemma they are invoking and explain how it preserves both directions of the k-SUM decision problem; otherwise the worst-case claim in Theorem 1.2 is not fully supported.
minor comments (4)
  1. [Section 3.4] The equality in the displayed total running time drops the contribution O~(n^{k2-r/2}) coming from the (1/sqrt(mu)) sqrt(m) T_upd term; the omitted term is dominated by the displayed max for the parameter choices in Table 1, but this should be stated explicitly in the text.
  2. [Section 3.2] The informal description says the walk stores one canonical representative per residue bucket, while the formal definition of D_{v,i} stores all entries in the bucket and R_{v,i}(s) returns the minimum; these two descriptions should be reconciled.
  3. [Theorem 4.2] The running time in the statement of Theorem 4.2 is printed as O*(32n/7); it should be O*(3^{2n/7}) to match the proof, where M = 3^{ceil(n/7)} and the total is O(n^2) * O~(M^2).
  4. [Section 1] The sentence 'The algorithm is not only faster for all k congruent to 3 or 6 modulo 7' is imprecise: Theorem 1.2 improves Tani's n^{k/3} for every k>3, and improves Schrottenloher's Phi_k only for k ≡ 3 or 6 mod 7; the sentence should be rephrased to avoid implying the only improvements are those residue classes.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the runtime bound is derived from an analytical optimization over the algorithm's own parameters, not from its inputs; the m-parameter inconsistency is a correctness typo, not a circular reduction.

full rationale

The paper's central claim (Theorem 1.2) is derived from a constructive algorithm that partitions the input into four blocks, samples subsets S2 and S4, uses a random-prime filter, and analyzes a quantum walk. The final exponent Psi_k is obtained by optimizing the expression max{r, (k1+k3)/3 + k2 - r/2} over block sizes and r. No external data, fitted constants, or benchmark-specific assumptions enter this optimization. The reference to Schrottenloher's Phi_k is only a notational benchmark; the proof does not invoke his algorithm or his random-instance guarantee as a premise. The random-prime lemma (Lemma 3.1) uses only the standard fingerprinting bound on input bit-length and Proposition 2.3, both parameter-free and external to the present result. The self-citations [BCKM24] and [BKM+24] appear only in the literature survey and are not load-bearing for the proof. The only notable defect is internal: Section 3.2 and Algorithm 1 set m = floor(n^{r/2}), while Equation (1) and the running-time analysis use m = n^r (e.g., the marked fraction m^2/n^{k2+k4} = Omega(n^{2r-k2-k4}) and the setup cost ~O(n^r)). If m = n^{r/2} were taken literally, the claimed runtime would not follow; however, this is an inconsistency or typo in the manuscript's parameter definition, not a circular derivation. The claimed reduction is a genuine algorithmic construction from stated assumptions, so the circularity score is 0.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The algorithm's runtime depends on the analytically chosen block sizes and sample exponent r, not on fitted data. The main axioms are standard quantum algorithmic primitives and number-theoretic estimates. The only notable issue is the m=n^{r/2} vs m=n^r inconsistency, which is a presentational error in the parameter definition.

free parameters (2)
  • r (sample-size exponent) = min{k2, 2/3(k2 + (k1+k3)/3)}, tabulated in Table 1
    Controls m, the size of the subsets S2 and S4 sampled from blocks 2 and 4. The manuscript says m=floor(n^{r/2}), but the complexity analysis (Eq (1), T_set, T_chk) is consistent only with m=Theta(n^r). This definitional inconsistency is the main technical wrinkle; the chosen r minimizes the worst-case exponent, so it is an analytical optimization rather than a data fit.
  • block sizes (k1,k2,k3,k4) = Table 1: k2=k4, k1=floor(ell/2), k3=ceil(ell/2), ell=k1+k3
    Partition of the k lists into four blocks. The exponents in Theorem 1.2 depend on these sizes; they are chosen to balance the claw-finding time and the walk factor. Not fitted to data.
assumptions (7)
  • domain assumption QRAQM model: coherent random access to any list entry costs polylog(m)
    Section 2.3 states the model; all dictionary operations (Theorem 2.4) and quantum walk costs assume it.
  • standard math Quantum walk search theorem (Szegedy 2004, MNRS11), Theorem 2.6
    Used in Section 3.4 to bound total time from T_set, T_upd, T_chk, and marked fraction mu.
  • standard math Johnson graph spectral gap delta = Omega(1/m) (Kachigar and Tillich 2017)
    Specializes Theorem 2.6 to the walk on J(X,m) x J(X,m); Section 2.3.
  • standard math Claw Finding algorithm (Tani 2009), Theorem 2.7
    Used inside the checker to find alpha1, alpha3 with F=G.
  • standard math Coherent dynamic dictionaries (Ambainis 2007, Theorem 2.4)
    Stores and updates residue buckets at each walk vertex.
  • standard math Random prime generation and prime number theorem
    Used in Proposition 2.3 and Lemma 3.1 to ensure random prime in [m log^2 n, 2m log^2 n] avoids differences of sums with high probability.
  • domain assumption Fingerprinting reduction: k-SUM instances can be assumed to have bit-length O(k log n)
    Section 2.1; needed for the O(log|z|/M) bound in Lemma 3.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Quantum Algorithms for Subset Sum and $k$-SUM." pith.science (2026). https://pith.science/paper/2ITUX3EY

@misc{pith2026260807309,
  author       = {Pith},
  title        = {Pith review of: Improved Quantum Algorithms for Subset Sum and $k$-SUM},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2ITUX3EY}},
  note         = {Machine review of arXiv:2608.07309}
}
abstract

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{\Phi_k})$ is known, where $$ \Phi_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{\Psi_k})$, where $$ \Psi_k=\Phi_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 53 canonical work pages

  1. [1]

    Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

    Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelh \"o fer, and Miklos Santha. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming . In European Symposium on Algorithms , volume 244 of LIPIcs , pages 6:1--6:18. Schloss Dagstuhl---Leibniz-Zentrum f \"u r Informatik, 2022

    work page 2022

  2. [2]

    PRIMES is in P

    Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P . Annals of Mathematics , 160(2):781--793, 2004

    work page 2004

  3. [3]

    Exact Weight Subgraphs and the k -Sum Conjecture

    Amir Abboud and Kevin Lewi. Exact Weight Subgraphs and the k -Sum Conjecture . In Automata, Languages, and Programming , volume 7965 of Lecture Notes in Computer Science , pages 1--12. Springer, 2013

    work page 2013

  4. [4]

    Losing Weight by Gaining Edges

    Amir Abboud, Kevin Lewi, and Ryan Williams. Losing Weight by Gaining Edges . In Algorithms---ESA , volume 8737 of Lecture Notes in Computer Science , pages 1--12. Springer, 2014

    work page 2014

  5. [5]

    Quantum Walk Algorithm for Element Distinctness

    Andris Ambainis. Quantum Walk Algorithm for Element Distinctness . SIAM Journal on Computing , 37(1):210--239, 2007

    work page 2007

  6. [6]

    Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

    Amir Abboud and Virginia Vassilevska Williams . Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems . In IEEE Symposium on Foundations of Computer Science , pages 434--443. IEEE Computer Society, 2014

    work page 2014

  7. [7]

    Improved Classical and Quantum Algorithms for Subset-Sum

    Xavier Bonnetain, R \'e mi Bricout, Andr \'e Schrottenloher, and Yixin Shen. Improved Classical and Quantum Algorithms for Subset-Sum . In Advances in Cryptology---ASIACRYPT , volume 12492 of Lecture Notes in Computer Science , pages 633--666. Springer, 2020

    work page 2020

  8. [8]

    Improved Generic Algorithms for Hard Knapsacks

    Anja Becker, Jean - S \'e bastien Coron, and Antoine Joux. Improved Generic Algorithms for Hard Knapsacks . In Advances in Cryptology---EUROCRYPT , volume 6632 of Lecture Notes in Computer Science , pages 364--385. Springer, 2011

    work page 2011

Show all 54 references
  1. [9]

    Kulikov, and Ivan Mihajlin

    Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin. Improved Space Bounds for Subset Sum . In European Symposium on Algorithms , volume 308 of LIPIcs , pages 21:1--21:17. Schloss Dagstuhl---Leibniz-Zentrum f \"u r Informatik, 2024

    2024

  2. [10]

    Quantum Algorithms for Element Distinctness

    Harry Buhrman, Christoph D \" u rr, Mark Heiligman, Peter H yer, Fr \' e d \' e ric Magniez, Miklos Santha, and Ronald de Wolf. Quantum Algorithms for Element Distinctness . SIAM Journal on Computing , 34(6):1324--1330, 2005

    2005

  3. [11]

    Quantum Amplitude Amplification and Estimation

    Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation . arXiv preprint quant-ph/0005055 , 2000

    2000 arXiv

  4. [12]

    Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer

    Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. Quantum Algorithms for the Subset-Sum Problem . In Post-Quantum Cryptography , volume 7932 of Lecture Notes in Computer Science , pages 16--33. Springer, 2013

    2013

  5. [13]

    Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, and Denil Sharipov

    Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, and Denil Sharipov. Computations with Polynomial Evaluation Oracle: Ruling Out Superlinear SETH-Based Lower Bounds . In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms , pag...

    2024

  6. [14]

    A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

    Karl Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1073--1084. SIAM, 2017

    2017

  7. [15]

    Servedio

    Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Subset Sum in time 2^ n/2 / poly (n) . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , volume 275 of LIPIcs , pages 39:1--39:18. Schloss Dagstuhl---Leibniz-Zentrum f \"u r In...

    2023

  8. [16]

    Benny Chor and Ronald L. Rivest. A Knapsack-Type Public Key Cryptosystem Based on Arithmetic in Finite Fields . IEEE Transactions on Information Theory , 34(5):901--909, 1988

    1988

  9. [17]

    Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems

    Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems . In Advances in Cryptology---CRYPTO , volume 7417 of Lecture Notes in Computer Science , page...

    2012

  10. [18]

    Recherches analytiques sur la th \'e orie des nombres premiers, I--III

    Charles - Jean de la Vall \'e e Poussin. Recherches analytiques sur la th \'e orie des nombres premiers, I--III . Annales de la Soci \'e t \'e scientifique de Bruxelles , 20:183--256, 281--362, 363--397, 1896

  11. [19]

    Chosen-Ciphertext Security from Subset Sum

    Sebastian Faust, Daniel Masny, and Daniele Venturi. Chosen-Ciphertext Security from Subset Sum . In Public-Key Cryptography---PKC , volume 9614 of Lecture Notes in Computer Science , pages 35--46. Springer, 2016

    2016

  12. [20]

    Quantum Algorithms for the k -XOR Problem

    Lorenzo Grassi, Mar \' a Naya - Plasencia, and Andr \'e Schrottenloher. Quantum Algorithms for the k -XOR Problem . In Advances in Cryptology---ASIACRYPT , volume 11272 of Lecture Notes in Computer Science , pages 527--559. Springer, 2018

    2018

  13. [21]

    Overmars

    Anka Gajentaan and Mark H. Overmars. On a Class of O(n^2) Problems in Computational Geometry . Computational Geometry , 5:165--185, 1995

    1995

  14. [22]

    Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search . In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , pages 212--219. ACM, 1996

    1996

  15. [23]

    Sur la distribution des z \'e ros de la fonction (s) et ses cons \'e quences arithm \'e tiques

    Jacques Hadamard. Sur la distribution des z \'e ros de la fonction (s) et ses cons \'e quences arithm \'e tiques . Bulletin de la Soci \'e t \'e Math \'e matique de France , 24:199--220, 1896

  16. [24]

    Finding an o(n^2 n) Algorithm Is Sometimes Hard

    Antonio Hern \'a ndez - Barrera. Finding an o(n^2 n) Algorithm Is Sometimes Hard . In Proceedings of the 8th Canadian Conference on Computational Geometry , pages 289--294. Carleton University Press, 1996

    1996

  17. [25]

    New Generic Algorithms for Hard Knapsacks

    Nick Howgrave - Graham and Antoine Joux. New Generic Algorithms for Hard Knapsacks . In Advances in Cryptology---EUROCRYPT , volume 6110 of Lecture Notes in Computer Science , pages 235--256. Springer, 2010

    2010

  18. [26]

    Subset Sum Quantumly in 1.17^n

    Alexander Helm and Alexander May. Subset Sum Quantumly in 1.17^n . In Conference on the Theory of Quantum Computation, Communication and Cryptography , volume 111 of LIPIcs , pages 5:1--5:15. Schloss Dagstuhl---Leibniz-Zentrum f \"u r Informatik, 2018

    2018

  19. [27]

    Quantum Search on Bounded-Error Inputs

    Peter H yer, Michele Mosca, and Ronald de Wolf. Quantum Search on Bounded-Error Inputs . In Automata, Languages and Programming , volume 2719 of Lecture Notes in Computer Science , pages 291--299. Springer, 2003

    2003

  20. [28]

    Computing Partitions with Applications to the Knapsack Problem

    Ellis Horowitz and Sartaj Sahni. Computing Partitions with Applications to the Knapsack Problem . Journal of the ACM , 21(2):277--292, 1974

    1974

  21. [29]

    Efficient Cryptographic Schemes Provably as Secure as Subset Sum

    Russell Impagliazzo and Moni Naor. Efficient Cryptographic Schemes Provably as Secure as Subset Sum . Journal of Cryptology , 9(4):199--216, 1996

    1996

  22. [30]

    3SUM, 3XOR, Triangles

    Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, Triangles . Algorithmica , 74(1):326--343, 2016

    2016

  23. [31]

    A Faster Algorithm for Pigeonhole Equal Sums

    Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums . In International Colloquium on Automata, Languages, and Programming , volume 297 of LIPIcs , pages 94:1--94:11. Schloss Dagstuhl---Leibniz-Zentrum f \"u r Informatik, 2024

    2024

  24. [32]

    Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach

    Antoine Joux and Karol W e grzycki. Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach . In International Symposium on Theoretical Aspects of Computer Science , volume 364 of LIPIcs , pages 57:1--57:19. Schloss Dagstuhl---Leibniz-Zent...

    2026

  25. [33]

    New Algorithms for Pigeonhole Equal Subset Sum

    Ce Jin, Ryan Williams, and Stan Zhang. New Algorithms for Pigeonhole Equal Subset Sum . In European Symposium on Algorithms , volume 351 of LIPIcs , pages 86:1--86:12. Schloss Dagstuhl---Leibniz-Zentrum f \"u r Informatik, 2025

    2025

  26. [34]

    Richard M. Karp. Reducibility Among Combinatorial Problems . In Complexity of Computer Computations , pages 85--103. Plenum Press, 1972

    1972

  27. [35]

    Higher Lower Bounds from the 3SUM Conjecture

    Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher Lower Bounds from the 3SUM Conjecture . In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1272--1287. SIAM, 2016

    2016

  28. [36]

    Quantum Information Set Decoding Algorithms

    Ghazal Kachigar and Jean - Pierre Tillich. Quantum Information Set Decoding Algorithms . In Post-Quantum Cryptography , volume 10346 of Lecture Notes in Computer Science , pages 69--89. Springer, 2017

    2017

  29. [37]

    k -SUM Hardness Implies Treewidth-SETH

    Michael Lampis. k -SUM Hardness Implies Treewidth-SETH . In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1916--1944. SIAM, 2026

    2026

  30. [38]

    Lenstra, Jr

    Hendrik W. Lenstra, Jr. Primality Testing with Gaussian Periods . In FSTTCS , volume 2556 of Lecture Notes in Computer Science , page 1. Springer, 2002

    2002

  31. [39]

    From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation Technique

    Yang Li. From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation Technique . Information , 16(10):887, 2025

    2025

  32. [40]

    J. C. Lagarias and Andrew M. Odlyzko. Solving Low-Density Subset Sum Problems . Journal of the ACM , 32(1):229--246, 1985

    1985

  33. [41]

    Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

    Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. Public-Key Cryptographic Primitives Provably as Secure as Subset Sum . In Theory of Cryptography , volume 5978 of Lecture Notes in Computer Science , pages 382--400. Springer, 2010

    2010

  34. [42]

    Wang, and R

    Andrea Lincoln, Virginia Vassilevska Williams , Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Trade-Offs for k -SUM . In International Colloquium on Automata, Languages, and Programming , volume 55 of LIPIcs , pages 58:1--58:14. Schloss Dagstuhl---Leibniz-Zent...

    2016

  35. [43]

    Merkle and Martin E

    Ralph C. Merkle and Martin E. Hellman. Hiding Information and Signatures in Trapdoor Knapsacks . IEEE Transactions on Information Theory , 24(5):525--530, 1978

    1978

  36. [44]

    Search via Quantum Walk

    Fr \'e d \'e ric Magniez, Ashwin Nayak, J \'e r \'e mie Roland, and Miklos Santha. Search via Quantum Walk . SIAM Journal on Computing , 40(1):142--164, 2011

    2011

  37. [45]

    Optimal Merging in Quantum k -XOR and k -XOR-SUM Algorithms

    Mar \' a Naya - Plasencia and Andr \'e Schrottenloher. Optimal Merging in Quantum k -XOR and k -XOR-SUM Algorithms . In Advances in Cryptology---EUROCRYPT , volume 12106 of Lecture Notes in Computer Science , pages 311--340. Springer, 2020

    2020

  38. [46]

    Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors

    Jesper Nederlof and Karol W e grzycki. Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors . In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1670--1683. ACM, 2021

    2021

  39. [47]

    Towards Polynomial Lower Bounds for Dynamic Problems

    Mihai P a tra s cu. Towards Polynomial Lower Bounds for Dynamic Problems . In Proceedings of the 42nd ACM Symposium on Theory of Computing , pages 603--610. ACM, 2010

    2010

  40. [48]

    Beating Meet-in-the-Middle for Subset Balancing Problems

    Tim Randolph and Karol W e grzycki. Beating Meet-in-the-Middle for Subset Balancing Problems . In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1314--1325. ACM, 2026

    2026

  41. [49]

    Improved Quantum Algorithms for the k -XOR Problem

    Andr \'e Schrottenloher. Improved Quantum Algorithms for the k -XOR Problem . In Selected Areas in Cryptography , volume 13203 of Lecture Notes in Computer Science , pages 311--331. Springer, 2021

    2021

  42. [50]

    A T=O(2^ n/2 ) , S=O(2^ n/4 ) Algorithm for Certain NP -Complete Problems

    Richard Schroeppel and Adi Shamir. A T=O(2^ n/2 ) , S=O(2^ n/4 ) Algorithm for Certain NP -Complete Problems . SIAM Journal on Computing , 10(3):456--464, 1981

    1981

  43. [51]

    Quantum Speed-Up of Markov Chain Based Algorithms

    Mario Szegedy. Quantum Speed-Up of Markov Chain Based Algorithms . In IEEE Symposium on Foundations of Computer Science , pages 32--41. IEEE Computer Society, 2004

    2004

  44. [52]

    Claw Finding Algorithms Using Quantum Walk

    Seiichiro Tani. Claw Finding Algorithms Using Quantum Walk . Theoretical Computer Science , 410(50):5285--5297, 2009

    2009

  45. [53]

    Finding, Minimizing, and Counting Weighted Subgraphs

    Virginia Vassilevska Williams and Ryan Williams. Finding, Minimizing, and Counting Weighted Subgraphs . SIAM Journal on Computing , 42(3):831--854, 2013

    2013

  46. [54]

    David A. Wagner. A Generalized Birthday Problem . In Advances in Cryptology---CRYPTO , volume 2442 of Lecture Notes in Computer Science , pages 288--303. Springer, 2002

    2002

Pith tools

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