Resilience for the Littlewood–Offord problem

Consider the sum X(ξ)=∑ni=1aiξi , where a=(ai)ni=1 is a sequence of non-zero reals and ξ=(ξi)ni=1 is a sequence of i.i.d. Rademacher random variables (that is, Pr[ξi=1]=Pr[ξi=−1]=1/2 ). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr[X=x] . In this paper we study a resilience version of the Littlewood-Offord problem: how many of the ξi is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems.