arXiv preprint ·
On the most informative Boolean function under noise
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Testing Implies Distance Estimation with Polynomial Loss
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
How Unbalanced Must a Latin Rectangle Be?
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.