Anticoncentration versus the number of subset sums

DOI10.19086/AIC.24872MaRDI QIDQ6358601arXivFDO

Authors Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date 19 January 2021

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

Abstract: Let

v e c w = (w_{1}, d o t s, w_{n}) i n m a t h b b R^{n}

. We show that for any

n^{- 2} l e e p s i l o n l e 1

, if [#{vec{xi} in {0,1}^{n}: langle vec{xi}, vec{w} angle = au} ge 2^{-epsilon n}cdot 2^{n}] for some

a u i n m a t h b b R

, then [#{langle vec{xi}, vec{w} angle : vec{xi} in {0,1}^{n}} le 2^{O(sqrt{epsilon}n)}.] This exponentially improves the

e p s i l o n

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.

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)