Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

DOI10.1145/3357713.3384308MaRDI QIDQ5144983zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Vasileios Nakos

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

convolutionoutput-sensitivepseudopolynomialrestricted sumsetsubset sum

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Output-sensitive algorithms for sumset and sparse polynomial multiplication
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• scientific article; zbMATH DE number 176777
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Parameterized top-\(K\) algorithms
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• scientific article; zbMATH DE number 139903
• Near-optimal linear decision trees for k-SUM and related problems

Cited in

(8)

• Faster algorithms for \(k\)-subset sum and variations
• Approximating subset sum ratio via subset sum computations
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Removing additive structure in 3SUM-based reductions
• Approximating subset sum ratio via partition computations
• Fast n-fold Boolean convolution via additive combinatorics
• Knapsack and subset sum with small items

This page was built for publication: Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

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