Change search
ReferencesLink to record
Permanent link

Direct link
Space-time tradeoffs for subset sum: An improved worst case algorithm
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Aalto Science Institute, Aalto University, Finland .ORCID iD: 0000-0001-8217-0158
2013 (English)In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, 45-56 p.Conference paper (Refereed)
Abstract [en]

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".

Place, publisher, year, edition, pages
Springer, 2013. no PART 1, 45-56 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7965 LNCS
Keyword [en]
Random composites, Randomness property, Space usage, Space-time tradeoffs, Subset sum, Subset sum problems, Trade space
National Category
Computer Science
URN: urn:nbn:se:kth:diva-134078DOI: 10.1007/978-3-642-39206-1_5ScopusID: 2-s2.0-84880309462ISBN: 978-364239205-4OAI: diva2:664573
40th International Colloquium on Automata, Languages, and Programming, ICALP 2013; Riga; Latvia; 8 July 2013 through 12 July 2013

QC 20131115

Available from: 2013-11-15 Created: 2013-11-15 Last updated: 2013-11-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link