Anticoncentration versus the Number of Subset Sums

DOI10.19086/AIC.24872MaRDI QIDQ5162870zbMATH OpenOpenAlexFDO

Authors Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date 5 November 2021

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

anticoncentration

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Inequalities; stochastic orderings (60E15) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Recommendations

• A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Subset sum in the absence of concentration
• Dense subset sum may be the hardest
• Worst-case analysis of the subset sum algorithm for bin packing.

Cites work

• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Optimal inverse Littlewood-Offord theorems
• Set partitioning via inclusion-exclusion
• The Littlewood-Offord problem and invertibility of random matrices

Cited in

(6)

• Rank deficiency of random matrices
• Singularity of discrete random matrices
• Friendly bisections of random graphs
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics
• Anticoncentration versus the number of subset sums

This page was built for publication: Anticoncentration versus the Number of Subset Sums

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