{"id":"arxiv/2611.05430","url":"https://arxiv.org/abs/2611.05430","tags":["cs.IT","math.CO"],"score":0,"title":"On the most informative Boolean function under noise","domain":"cs.IT","source":"arxiv","authors":["Dimiter Kramer","Mert Saglam"],"reviews":0,"subject":"cs.IT","summary":"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 $\\mathbf{I}(C:X)\\le \\mathbf{I}(Y_1:X)$ for all $p\\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}