Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
From MaRDI portal
Publication:4687248
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
subset sumspace-time trade-offexponential time algorithmsexact exponential time algorithmsspace-efficient algorithms\(k\)-sumfine-grained complexity
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