Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems

DOI10.1137/17M1158203zbMath1400.68259arXiv1612.02788OpenAlexW2564022051MaRDI QIDQ4687248

Jesper Nederlof, Shashwat Garg, Nikhil Vyas, Nikhil Bansal

Publication date: 11 October 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

subset sumspace-time trade-offexponential time algorithmsexact exponential time algorithmsspace-efficient algorithms\(k\)-sumfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Related Items (2)

The Modular Subset-Sum Problem and the size of deletion correcting codes ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Pseudorandom generators for space-bounded computation
• Improved low-density subset sum algorithms
• On read-once vs. multiple access to randomness in logspace
• Parallel collision search with cryptanalytic applications
• The space complexity of approximating the frequency moments
• Parametrized and exact computation. First international workshop, IWPEC 2004, Bergen, Norway, September 14--17, 2004. Proceedings.
• Efficient cryptographic schemes provably as secure as subset sum
• Saving space by algebraization
• Hardness Preserving Constructions of Pseudorandom Functions
• Reducing a Target Interval to a Few Exact Queries
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Space-Efficient Randomized Algorithms for K-SUM
• Improved Generic Algorithms for Hard Knapsacks
• Dynamic Programming Treatment of the Travelling Salesman Problem
• New Generic Algorithms for Hard Knapsacks
• Solving low-density subset sum problems
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Computing Partitions with Applications to the Knapsack Problem
• An upper bound for codes in a two-access binary erasure channel (Corresp.)
• Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
• Dense Subset Sum may be the hardest
• New algorithms and lower bounds for circuits with linear threshold gates
• Homomorphic Hashing for Sparse Coefficient Extraction
• Faster space-efficient algorithms for subset sum and k-sum
• Algorithmic Cryptanalysis
• Parameterized and Exact Computation
• Computational Complexity
• Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
• STACS 2005

This page was built for publication: Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems