The sharp small-noise constant for weighted majority
Flip each coordinate of a uniform point of {−1,1}^n independently with probability ε. Peres proved that a linear threshold function then changes its value with probability at most 2√ε, with asymptotic constant √(2/π), and asked whether the constant can be lowered to 2/π, the value for simple majority. We prove that every linear threshold function changes with probability at most (2/π)√ε + Cε^(3/5) for an absolute constant C. This proves the weak form of the Majority Is Least Stable conjecture recorded in O'Donnell's list of open problems. With the weights normalized so that their squares sum to one, the sequences of linear threshold functions that attain the constant asymptotically are exactly those in which the threshold b tends to zero and, for every fixed positive c, the weights of size at least c√ε carry a vanishing share of the squared norm. Peres's bound holds for independent symmetric real inputs; for centered inputs with no atom at zero no bound C√ε uniform over the laws holds.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24375410
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint