## Abstract

Consider the sum X(ξ)=∑_{i=1}^{n}a_{i}ξ_{i}, where a=(a_{i})_{i=1}^{n} is a sequence of non-zero reals and ξ=(ξ_{i})_{i=1}^{n} 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]. 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, demonstrating an interesting connection to the notion of an additive basis from additive combinatorics. We also present several interesting open problems.

Original language | English (US) |
---|---|

Pages (from-to) | 93-99 |

Number of pages | 7 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 61 |

DOIs | |

State | Published - Aug 2017 |

## Keywords

- Additive basis
- Anti-concentration
- Littlewood-Offord
- Resilience

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics