Resilience for the Littlewood–Offord problem

Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood–Offord problem. Advances in Mathematics. 319, 292–312.


Journal Article | Published | English

Scopus indexed
Author
Bandeira, Afonso S.; Ferber, Asaf; Kwan, Matthew AlanIST Austria
Abstract
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.
Publishing Year
Date Published
2017-10-15
Journal Title
Advances in Mathematics
Volume
319
Page
292-312
ISSN
IST-REx-ID

Cite this

Bandeira AS, Ferber A, Kwan MA. Resilience for the Littlewood–Offord problem. Advances in Mathematics. 2017;319:292-312. doi:10.1016/j.aim.2017.08.031
Bandeira, A. S., Ferber, A., & Kwan, M. A. (2017). Resilience for the Littlewood–Offord problem. Advances in Mathematics. Elsevier. https://doi.org/10.1016/j.aim.2017.08.031
Bandeira, Afonso S., Asaf Ferber, and Matthew Alan Kwan. “Resilience for the Littlewood–Offord Problem.” Advances in Mathematics. Elsevier, 2017. https://doi.org/10.1016/j.aim.2017.08.031.
A. S. Bandeira, A. Ferber, and M. A. Kwan, “Resilience for the Littlewood–Offord problem,” Advances in Mathematics, vol. 319. Elsevier, pp. 292–312, 2017.
Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood–Offord problem. Advances in Mathematics. 319, 292–312.
Bandeira, Afonso S., et al. “Resilience for the Littlewood–Offord Problem.” Advances in Mathematics, vol. 319, Elsevier, 2017, pp. 292–312, doi:10.1016/j.aim.2017.08.031.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1609.08136

Search this title in

Google Scholar