PreprintCC BY 4.0arXiv
On the most informative Boolean function under noise
Abstract
Let X be a uniform random bit string and Y be obtained by flipping each bit of X independently with probability p. Let C be a random bit obtained as a function of Y. We show that I(C:X)≤ I(Y1:X) for all p∈[0,1], which resolves a conjecture posed by Courtade and Kumar in 2013.
Related
- A Proof of the Most Informative Boolean Function Conjecture
- Dictators are most informative
- The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions
- The Noise Is the Signal: Correlated Sampling Error Is Rank-Informative for Proxy Metric Selection
- An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
BibTeX
@misc{kramer2026most,
title = {{On the most informative Boolean function under noise}},
author = {Dimiter Kramer and Mert Saglam},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05430},
eprint = {2611.05430},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05430},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the most informative Boolean function under noise
AU - Dimiter Kramer
AU - Mert Saglam
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05430
UR - https://arxiv.org/abs/2611.05430
AB - Let X be a uniform random bit string and Y be obtained by flipping each bit of X independently with probability p. Let C be a random bit obtained as a function of Y. We show that I(C:X)≤ I(Y_1:X) for all p∈[0,1], which resolves a conjecture posed by Courtade and Kumar in 2013.
ER -