Dense Subset Sum may be the hardest
From MaRDI portal
Publication:4601865
DOI10.4230/LIPIcs.STACS.2016.13zbMath1388.68079arXiv1508.06019MaRDI QIDQ4601865
Mikko Koivisto, Per Austrin, Jesper Nederlof, Petteri Kaski
Publication date: 24 January 2018
Full work available at URL: https://arxiv.org/abs/1508.06019
additive combinatoricssubset sumexponential-time algorithmLittlewood-Offord problemhomomorphic hashing
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
A short note on Merlin-Arthur protocols for subset sum ⋮ Approximating subset sum ratio via subset sum computations ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Unnamed Item ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
This page was built for publication: Dense Subset Sum may be the hardest
