Reproduce “On the most informative Boolean function under noise” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Dimiter Kramer, Mert Saglam
The authors prove that for a uniformly random n-bit string independently corrupted by bit flips with probability p, no Boolean function of the noisy string reveals more about the original than one noisy coordinate. They establish this for every p in [0,1], resolving the Courtade–Kumar conjecture. The result concerns discrete inputs; their bound does not extend to the continuous analogue.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.