Space-time tradeoffs for subset sum: an improved worst case algorithm

DOI10.1007/978-3-642-39206-1_5MaRDI QIDQ5326549zbMATH OpenOpenAlexFDO

Authors Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.0609

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Abstract: The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the SUBSET SUM problem. In the random-instance setting, however, improved tradeoffs exist. In particular, the recently discovered dissection method of Dinur et al. (CRYPTO 2012) yields a significantly improved space--time tradeoff curve for instances with strong randomness properties. Our main result is that these strong randomness assumptions can be removed, obtaining the same space--time tradeoffs in the worst case. We also show that for small space usage the dissection algorithm can be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space--time controls into the algorithm by means of a "bailout mechanism".

Recommendations

• A near-linear pseudopolynomial time algorithm for subset sum
• Faster space-efficient algorithms for subset sum and k-sum
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Space-efficient randomized algorithms for k-sum
• Parallel time and space upper-bounds for the subset-sum problem

Cited in

(8)

• Efficient dissection of bicomposite problems with cryptanalytic applications
• Space-efficient randomized algorithms for k-sum
• Improved information set decoding for code-based cryptosystems with constrained memory
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Faster space-efficient algorithms for subset sum and k-sum
• Improved space-time tradeoffs for \(k\)SUM
• Equal-subset-sum faster than the meet-in-the-middle
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice

This page was built for publication: Space-time tradeoffs for subset sum: an improved worst case algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326549)