Resilience for the Littlewood-Offord Problem

Afonso S. Bandeira, Asaf Ferber, Matthew Kwan

Research output: Contribution to journalArticle

Abstract

Consider the sum X(ξ)=∑i=1naiξi, where a=(ai)i=1n is a sequence of non-zero reals and ξ=(ξi)i=1n 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 languageEnglish (US)
Pages (from-to)93-99
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume61
DOIs
StatePublished - Aug 2017

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Resilience for the Littlewood-Offord Problem'. Together they form a unique fingerprint.

Cite this