Resilience for the Littlewood-Offord problem
Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood-Offord problem. Electronic Notes in Discrete Mathematics. 61, 93–99.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Bandeira, Afonso S.;
Ferber, Asaf;
Kwan, Matthew AlanISTA 
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-08-01
Journal Title
Electronic Notes in Discrete Mathematics
Volume
61
Page
93-99
ISSN
IST-REx-ID
Cite this
Bandeira AS, Ferber A, Kwan MA. Resilience for the Littlewood-Offord problem. Electronic Notes in Discrete Mathematics. 2017;61:93-99. doi:10.1016/j.endm.2017.06.025
Bandeira, A. S., Ferber, A., & Kwan, M. A. (2017). Resilience for the Littlewood-Offord problem. Electronic Notes in Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.endm.2017.06.025
Bandeira, Afonso S., Asaf Ferber, and Matthew Alan Kwan. “Resilience for the Littlewood-Offord Problem.” Electronic Notes in Discrete Mathematics. Elsevier, 2017. https://doi.org/10.1016/j.endm.2017.06.025.
A. S. Bandeira, A. Ferber, and M. A. Kwan, “Resilience for the Littlewood-Offord problem,” Electronic Notes in Discrete Mathematics, vol. 61. Elsevier, pp. 93–99, 2017.
Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood-Offord problem. Electronic Notes in Discrete Mathematics. 61, 93–99.
Bandeira, Afonso S., et al. “Resilience for the Littlewood-Offord Problem.” Electronic Notes in Discrete Mathematics, vol. 61, Elsevier, 2017, pp. 93–99, doi:10.1016/j.endm.2017.06.025.
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
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1609.08136
Google Scholar