🔢 mathematics

Deterministic identification for Bernoulli channels and related channels with continuous input

This paper resolves the long-standing open problem of deterministic identification capacity for Bernoulli and related continuous-input channels by introducing a novel "galaxy" code construction that proves the tight converse bound of $\dot{C}_{\text{DI}}(W) = \frac{1}{2}$ and establishes improved reliability function bounds for the rate-error tradeoff.

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Finding a Needle in a Haystack vs. Checking a Name Tag

Imagine you are at a massive party with millions of people.

The Old Way (Shannon Transmission): You want to tell a specific person, "Hey, I am Bob." You have to shout your whole story, your address, and your favorite color so they can reconstruct your identity perfectly. This takes a lot of time and energy.
The New Way (Identification): You don't need to tell them who you are. You just need to answer a simple "Yes" or "No" to a specific question: "Are you Bob?"

In the world of information theory, this is called Identification. The paper focuses on a specific type called Deterministic Identification (DI), where you don't use random tricks or luck to find the answer; you use a strict, guaranteed method.

The Problem: The "Gap" in the Math

For a long time, mathematicians knew that for certain types of communication channels (like those with continuous inputs, such as sound waves or light intensity), you could fit way more "Yes/No" questions into a message than you could fit full stories.

However, there was a frustrating gap in the math:

The Best Guess (Lower Bound): We knew we could definitely fit at least a certain amount of questions.
The Theoretical Limit (Upper Bound): We knew we could never fit more than double that amount.
The Gap: We didn't know the exact number. It was like knowing a jar holds between 100 and 200 marbles, but not knowing if it holds 101, 150, or 199.

This paper closes that gap. It proves the jar holds exactly 150 marbles (mathematically speaking, the capacity is exactly 1/2).

The Solution: A Multi-Layer "Russian Nesting Doll" Strategy

The authors solved this by building a new kind of code (a set of instructions for sending messages). Instead of using the old, messy methods, they used a clever geometric trick inspired by how shapes behave in very high dimensions.

The Analogy: The Sea Urchin and the Cube

The Shape of the Problem: Imagine the possible messages as points inside a giant, multi-dimensional cube (like a box).
The Old Mistake: Previous methods tried to pack these points like oranges in a crate. They worked okay, but they left a lot of empty space.
The New Trick: The authors realized that in very high dimensions, a sphere (a ball) doesn't look like a smooth ball. It looks like a Sea Urchin. It has a round core, but thousands of long, sharp "spines" sticking out in every direction.
The Magic: The "spines" of this Sea Urchin actually poke inside the corners of the cube where the messages live.
- The authors built their code on the surface of this "Sea Urchin" sphere.
- Because the spines reach deep into the corners of the cube, they can fit many more points (messages) inside the allowed space than anyone thought possible.

The "Bernoulli" Channel: The Simple Switch

The paper focuses heavily on the Bernoulli channel.

The Analogy: Think of a light switch that is slightly broken. If you set it to "50%," it flickers randomly between On and Off. If you set it to "80%," it stays On most of the time but flickers Off occasionally.
The paper proves that even with this flickering, uncertain switch, you can use the "Sea Urchin" strategy to pack the maximum number of "Yes/No" questions possible.

The Ripple Effect: One Solution Fits All

The most powerful part of the paper is that once they solved the puzzle for the Bernoulli channel (the flickering light switch), they showed it solves the puzzle for almost everything else too.

The Reduction: They proved that many complex channels (like the Poisson channel used in fiber optics, or the Gaussian channel used in radio) can be mathematically "squashed" down to look like the simple Bernoulli switch.
The Result: Because they solved the Bernoulli puzzle, they automatically solved the puzzle for the Poisson and Gaussian channels.
The Conclusion: For all these channels, the maximum speed at which you can send "Yes/No" identification messages is exactly 1/2 (in a specific mathematical scale called "linearithmic").

The Trade-off: Speed vs. Accuracy

The paper also looked at a trade-off: How fast can you go if you are willing to make a few mistakes?

If you demand perfect accuracy (zero errors), you have to slow down.
If you allow a tiny, vanishingly small chance of error, you can go much faster.
The authors showed that their new "Sea Urchin" code is so efficient that it hits the theoretical speed limit almost perfectly, even when you allow for tiny errors.

Summary of Claims

Closed the Gap: They proved the exact capacity for deterministic identification on Bernoulli, Poisson, and Gaussian channels is 1/2.
New Method: They used a geometric construction (multi-layer spheres) instead of old statistical methods.
Universality: They showed that if a channel's output looks like a continuous curve (like a line or a smooth shape), this 1/2 capacity limit applies.
Reliability: They proved their code works reliably, with errors disappearing as the message gets longer.

What the paper does NOT claim:

It does not claim this will immediately change your phone or internet speed tomorrow.
It does not discuss medical applications or specific hardware implementations.
It does not claim this works for every type of channel (specifically, it notes that channels with very complex, high-dimensional shapes might behave differently).

In short, the paper is a mathematical proof that we have found the absolute limit of how many "Yes/No" questions we can send over certain types of communication lines, and we found a perfect way to do it.

Technical Summary: Deterministic Identification for Bernoulli Channels and Related Continuous-Input Channels

Problem Statement
The paper addresses the problem of Deterministic Identification (DI) over memoryless channels with continuous input alphabets. In the DI paradigm, introduced by Ahlswede and Dueck, a receiver tests whether a transmitted message $i$ coincides with a specific message $j$ of its choice, rather than decoding the full message. While DI over discrete memoryless channels (DMCs) supports only linear message growth ( $\log N \sim n$ ), channels with continuous inputs (such as Gaussian, Poisson, and Bernoulli) allow for "linearithmic" growth ( $\log N \sim n \log n$ ).

Despite this known scaling, the exact linearithmic DI capacity, denoted $\dot{C}_{DI}(W)$ , has remained an open problem for a broad class of channels. Specifically, for the Bernoulli channel ( $B$ ), Poisson channel ( $P$ ), and Additive White Gaussian Noise (AWGN) channel ( $G$ ), the capacity was known to be bounded between $1/4$ and $1/2$ :
$\frac{1}{4} \leq \dot{C}_{DI}(W) \leq \frac{1}{2}$
This persistent gap between the best-known achievability bounds (based on typicality arguments) and the converse bounds (based on Minkowski dimension) had not been closed. Furthermore, a similar gap existed for the rate-reliability tradeoff in the regime of small error exponents.

Methodology
The authors propose a novel coding scheme that departs from traditional typicality-based arguments, relying instead on high-dimensional geometric concentration phenomena. The methodology proceeds in three main stages:

Geometric Code Construction: Inspired by a recent construction for AWGN channels, the authors design a multi-layer geometric arrangement of codewords on the surface of high-dimensional spheres. The codebook is constructed sequentially through $L$ layers. Each layer consists of a $d$ -angle-dense arrangement of points in a subspace orthogonal to the vector connecting the center of the previous layer to the current layer's center. This structure ensures that codewords in inner layers project onto specific directions with high concentration.
Noise Concentration Analysis: A critical step involves proving that the noise in the Bernoulli channel, despite being input-dependent and non-isotropic, exhibits a concentration property similar to Gaussian noise. Specifically, the authors prove (Proposition 3) that the projection of the Bernoulli noise vector onto any fixed direction is exponentially unlikely to be large. This allows the use of the same geometric decoding strategy (sequential testing of projections against thresholds) used for Gaussian channels.
Expurgation and Reduction:
- Expurgation: The primitive codebook constructed on a high-dimensional sphere initially contains points outside the valid input space (the unit hypercube for the Bernoulli channel). The authors demonstrate that in high dimensions, the surface of a sphere of appropriate radius overlaps significantly with the "spines" of the hypercube near its vertices. By applying a random rotation, they show that an exponentially large fraction of the codewords lie within the valid input space, allowing for the selection of a valid sub-code.
- Reduction: The authors establish a reduction principle (Lemma 2) showing that any channel whose image contains a non-trivial continuous curve of output distributions can simulate a restricted Bernoulli channel via classical pre- and post-processing. This extends the capacity results from the Bernoulli channel to a broad family of "Bernoulli-reducible" channels.

Key Contributions and Results

Exact Capacity for Bernoulli Channels: The paper constructs a reliable DI code for the Bernoulli channel that achieves a linearithmic rate of $1/2$ . Combined with the existing converse bound, this establishes the exact capacity:
$\dot{C}_{DI}(B) = \frac{1}{2}$
Resolution of the Capacity Gap for Broad Classes: By extending the construction to restricted Bernoulli channels ( $B|[a,b]$ $B ∣ [a, b]$ ) and utilizing the reduction lemma, the authors prove that the capacity is $1/2$ $1/2$ for any channel $W$ $W$ whose image contains a continuous curve. This includes:
- The Poisson channel ( $P$ ), establishing $\dot{C}_{DI}(P) = 1/2$ .
- The AWGN channel ( $G$ ), reproducing the recent result $\dot{C}_{DI}(G) = 1/2$ .
- Any channel $Q$ with continuous input, discrete output, and Minkowski dimension $d_M = 1$ .
- Generally, for any Bernoulli-reducible channel, $\dot{C}_{DI}(W) = 1/2$ .
Rate-Reliability Tradeoff: The authors analyze the tradeoff between the linear rate and the error exponents. They derive improved lower bounds on the reliability function, showing that in the regime of small error exponents (sub-exponential error decay), the achievable rate matches the known converse bound at the leading order. This closes the gap previously observed in rate-reliability analyses for these channels.
Explicit Construction for Poisson Channels: While the general result for the Poisson channel is existential via reduction, the paper provides an explicit, capacity-achieving geometric construction for the Poisson channel under a peak power constraint.

Significance
The paper claims to close the long-standing capacity gap for deterministic identification in the linearithmic regime for a broad class of continuous-input channels. The significance lies in:

Tightness of Bounds: It proves that the converse bound of $1/2$ is tight for channels with continuous curves in their image, resolving a problem open since the early investigations of DI.
Methodological Shift: It demonstrates that geometric constructions based on noise concentration are superior to typicality-based arguments for DI, as the latter were responsible for the persistent gap in achievability.
Universality: The results highlight a surprising universality in DI capacity. Unlike Shannon transmission capacity, which depends on specific channel parameters (e.g., SNR, power constraints), the linearithmic DI capacity for this broad class of channels is a universal constant ( $1/2$ ), governed solely by the geometric dimension of the channel image.
Extension to Input-Dependent Noise: The work extends geometric concentration techniques, previously thought to be specific to isotropic Gaussian noise, to channels with strong input-dependent noise (Bernoulli and Poisson), suggesting a unifying geometric framework for DI.