Anticoncentration versus the number of subset sums

DOI10.19086/AIC.24872zbMATH Open1529.68185arXiv2101.07726MaRDI QIDQ6358601FDOQ6358601

Mehtaab Sawhney, Ashwin Sah, Vishesh Jain

Publication date: 19 January 2021

Abstract: Let $vecw=(w_1,dots,w_n)inmathbb{R}^n$. We show that for any $n^{-2}leepsilonle1$, if [#{vec{xi} in {0,1}^{n}: langle vec{xi}, vec{w} angle = au} ge 2^{-epsilon n}cdot 2^{n}] for some $auinmathbbR$, then [#{langle vec{xi}, vec{w} angle : vec{xi} in {0,1}^{n}} le 2^{O(sqrt{epsilon}n)}.] This exponentially improves the $epsilon$ dependence in a recent result of Nederlof, Pawlewicz, Swennenhuis, and Wk{e}grzycki and leads to a similar improvement in the parameterized (by the number of bins) runtime of bin packing.

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Arithmetic combinatorics; higher degree uniformity (11B30)

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 Q6358601)