On the most informative Boolean function under noise

Dimiter Kramer; Mert Saglam

AI summary · arXiv: 2611.05430v1 · cs.IT

On the most informative Boolean function under noise

Dimiter Kramer, Mert Saglam

Original paper Submitted to arXiv on 03 Nov. 2026 17 pages, 2 figures License: CC BY 4.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves that no Boolean function of a bit-flipped uniform string is more informative about the original string than a single noisy bit.

Based on the abstract only: check the details in the original paper.

Question

For a uniform random bit string X and its independently bit-flipped version Y, can any Boolean function C of Y contain more information about X than one coordinate of Y? The paper resolves the Courtade–Kumar conjecture on this question.

Method

The authors consider X uniform and form Y by flipping each bit independently with probability p, for p in [0,1]. They prove that for any bit C obtained as a function of Y, the mutual information I(C:X) is at most I(Y₁:X).

Findings

Result For every p in [0,1], the information that C provides about X is bounded above by the information in one coordinate of Y.
See the passage in the paper
We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$
Authors’ interpretation The result resolves the conjecture posed by Courtade and Kumar in 2013.
See the passage in the paper
which resolves a conjecture posed by Courtade and Kumar in 2013.

Limitations

The available abstract does not specify the string length or provide details of the proof, so the scope and technical assumptions beyond the stated setup cannot be assessed from this source.

Why it matters

The result settles the stated conjecture by establishing a single-coordinate upper bound on the information obtainable through any Boolean function of the noisy string.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Boolean functions mutual information noisy inputs independent bit-flip noise Courtade–Kumar conjecture

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

In “On the Most Informative Boolean Function Under Noise,” Dimiter Kramer and Mert Saglam study how much information a Boolean function can preserve about a noisy version of its input. Let $X$ be a uniformly random bit string, and let $Y$ be formed by independently flipping each bit of $X$ with probability $p$. For a single-bit Boolean function $C$ of $Y$, the authors ask whether $C$ can be more informative about $X$ than one coordinate of $Y$. They show that, for every $p \in [0,1]$, the mutual information between $C$ and $X$ is no greater than the mutual information between the first coordinate of $Y$ and $X$. Thus, among all single-bit Boolean functions of the noisy input, a coordinate function is at least as informative about the original input as any other choice. This result resolves a conjecture posed by Courtade and Kumar in 2013. The supplied material consists only of the title and abstract. It does not describe the proof, the authors’ methods, or any further examples, bounds, or corollaries, so those details cannot be summarized reliably. The abstract’s main quantitative claim is the universal inequality for all noise probabilities in $[0,1]$. At $p=0$, $Y=X$; at $p=1$, every bit is flipped deterministically. In both cases, a coordinate of $Y$ determines the corresponding bit of $X$. For intermediate noise levels, the theorem states that no more complicated single-bit encoding of $Y$ provides greater mutual information about $X$ than a coordinate does. As stated in the abstract, the result applies to uniformly random bit strings, independent bit flips with a common probability, and functions with a single-bit output. The supplied material does not establish whether analogous results hold for nonuniform inputs, correlated or unequal noise, or outputs with more than one bit.

When a Noisy Bit String Still Tells Us Something

Imagine sending a string of bits through a channel that randomly flips some of them. Afterward, you must report just one bit about the altered string. Which choice tells someone the most about the original message: selecting one coordinate, or combining several coordinates into a more elaborate Boolean function?

In “On the most informative Boolean function under noise,” Dimiter Kramer and Mert Saglam answer this question with a striking general result. For the setting they study, no single-bit Boolean function of the noisy string preserves more information about the original input than simply reporting one coordinate of the noisy string.

The setup: a message passes through noise

Let X be a uniformly random bit string. A noisy version, Y, is created by flipping each bit of X independently with probability p. When p is small, most bits are likely to remain unchanged. As p increases, the string becomes less reliable; at p = 1, every bit is flipped.

Now consider a function C that takes the entire noisy string Y as input and produces a single output bit. The function might select one coordinate, or it might combine information from multiple coordinates according to some Boolean rule. The question is how informative that output is about X.

The paper measures this using mutual information: a quantity that captures how much learning one variable reduces uncertainty about another. The authors compare the information that C(Y) provides about X with the information provided by the first coordinate of Y.

The central result

Kramer and Saglam show that for every noise probability from 0 to 1, the mutual information between C(Y) and X is no greater than the mutual information between the first coordinate of Y and X. In other words, among all single-bit Boolean functions of the noisy input, a coordinate function is at least as informative about the original input as any alternative.

The claim is notable because a function can inspect the whole noisy string before producing its one-bit answer. It might seem that combining several coordinates could help recover a useful signal. The theorem says that, under the specified conditions, such a more complicated single-bit summary cannot beat the simple strategy of reporting one coordinate.

Why the endpoints are intuitive

The result includes the two extreme noise levels. At p = 0, nothing is flipped, so Y equals X. A coordinate of Y directly reveals the corresponding coordinate of X. At p = 1, every bit is flipped deterministically, and a coordinate of Y still determines the matching bit of X: flipping it back recovers the original value.

The more interesting part is what the theorem says between these endpoints. When each bit is flipped with an intermediate probability, the channel introduces genuine uncertainty. Even then, no more elaborate Boolean function with a single-bit output provides more mutual information about the original input than a coordinate does.

Why this question matters

The result addresses a basic problem in information theory and Boolean-function analysis: how should a limited-output summary be designed when its input has been corrupted? A single bit cannot retain everything about a long string, so the choice of summary matters. The theorem gives a clean answer for this particular model: if the summary must be one Boolean output, selecting a coordinate is optimal in the stated comparison.

It also resolves a conjecture posed by Courtade and Kumar in 2013. That connection places the result within a broader effort to understand how information behaves when random noise alters data and a function compresses it.

What the result does—and does not—cover

The conclusion rests on specific assumptions. The input string is uniformly random, each bit is flipped independently, and every bit has the same flip probability. The function produces a single bit. Within that framework, the inequality holds for all p in the interval from 0 to 1.

The supplied abstract does not establish whether the same conclusion holds if the input bits are nonuniform, if noise is correlated across coordinates, or if different bits have different flip probabilities. Nor does it settle what happens when the function is allowed to output more than one bit. Those are natural questions, but they should not be treated as results of this paper based on the available description.

A simple choice with a strong guarantee

The paper’s main message is both precise and easy to state: when a uniformly random bit string is independently corrupted by equal-probability bit flips, no single-bit Boolean function of the corrupted string is more informative about the original string than one coordinate is. In a setting where clever combinations might seem promising, the coordinate wins—across the full range of noise probabilities.

Created on 09 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Computing beyond AI this week" of 9 November 2026. Computing beyond AI this week: What noise reveals, and what guarantees conceal

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

On the most informative Boolean function under noise

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

When a Noisy Bit String Still Tells Us Something

The setup: a message passes through noise

The central result

Why the endpoints are intuitive

Why this question matters

What the result does—and does not—cover

A simple choice with a strong guarantee

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Prior work it builds on

Go further

Cite this paper (BibTeX)