🔢 mathematics

Beyond Identification: Computing Boolean Functions via Channels

This paper generalizes the identification-via-channels framework by introducing the concept of computation capacity to determine the asymptotic relationship between message length and codeword length required for a receiver to reliably recover a Boolean function from a known class, providing tight achievability and converse results based on the functions' Hamming weights.

Original authors: Jingge Zhu, Matthias Frey

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingge Zhu, Matthias Frey

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

Imagine you are running a massive, high-stakes game of "Guess the Rule" over a very noisy walkie-talkie.

The Setup: The Noisy Walkie-Talkie

In a normal phone call, you want to send a whole message (like "Meet me at 5 PM") and have the other person hear it perfectly. This is what traditional communication (Shannon's theory) is about: sending the entire message.

But in this paper, the authors ask a different question: What if the person on the other end doesn't need the whole message? What if they only need to know the answer to a specific Yes/No question about the message?

The Real-World Example: The Electric Car Battery

Think of an electric car. It has sensors checking the battery:

Is it too hot?
Is the voltage too low?
Is the voltage too high?

The car sends a 3-bit code (like 101) to the central computer.

In "Driving Mode," the computer only cares: "Is it too hot OR is the voltage too high?" (It doesn't care about the low voltage).
In "Charging Mode," the computer only cares: "Is it too hot AND is the voltage too low?"

The car (the transmitter) doesn't know which mode the computer is in. It just sends the raw data. The computer (the receiver) knows the "rule" (the Boolean function) it wants to check, but the car doesn't. The goal is for the computer to figure out the answer to its specific question, even if the walkie-talkie is full of static.

The Big Question: How much data can we squeeze through?

The authors are trying to find the limit of this system.

$m$ : How many bits of information the car has (the message length).
$n$ : How long the signal is that the car sends (the channel use).

The question is: If I give you a fixed amount of time to send a signal ( $n$ ), how big of a message ( $m$ ) can you send so that the receiver can still reliably answer their specific Yes/No question?

The "Secret Sauce": The Complexity of the Question

The paper discovers that the answer depends entirely on how complicated the question is. They measure this complexity by something called "Hamming Weight."

Think of "Hamming Weight" as the number of different situations where the answer is "YES" (True).

The "Needle in a Haystack" (Low Weight):
- The Question: "Is the message exactly 10101?"
- The Weight: Only 1 situation out of millions makes this true.
- The Result: This is like the old "Identification" problem. Because the answer is so rare, you can send a massive amount of data. The message size ( $m$ ) can grow exponentially compared to the signal length ( $n$ ). It's like finding a needle in a haystack; you don't need to describe the whole haystack, just point to the needle.
The "Common Sense" Check (High Weight):
- The Question: "Is the message greater than 50%?" (Or "Is the majority of bits 1?").
- The Weight: Half of all possible situations make this true.
- The Result: This is like normal communication. You can't cheat the physics. The message size ( $m$ ) can only grow linearly with the signal length ( $n$ ). You have to send the whole story to get the answer.
The "Middle Ground" (The Discovery):
The authors found that as you change the question from "Needle in a Haystack" to "Common Sense," the capacity doesn't just jump from "Exponential" to "Linear." There is a whole spectrum in between!
- Depending on the question, the message size can grow polynomially (like $n^2$ ), quasi-linearly (like $n \log n$ ), or sub-exponentially.

The Analogy: The Library and the Librarian

Imagine a giant library (the message space) with $2^m$ books.

Scenario A (Low Weight): The librarian asks, "Is Book #42 in the library?"
- The librarian only needs to check one specific spot. The author can send a code that uniquely identifies any book in the library, even if the library is astronomically huge.
Scenario B (High Weight): The librarian asks, "Are there more than 50% red books in the library?"
- The librarian needs to know the general composition of the whole library. The author has to send a detailed summary of the whole collection.
Scenario C (Medium Weight): The librarian asks, "Is the book number a prime number?"
- This is somewhere in the middle. The author can send a message larger than a normal summary, but not as huge as the "Needle" scenario.

Why This Matters

This paper generalizes a famous concept called "Identification via Channels." Before this, we mostly knew two extremes:

Identification: "Is it this specific thing?" (Super efficient, exponential growth).
Transmission: "Tell me everything." (Standard efficiency, linear growth).

This paper fills in the gaps. It tells engineers and computer scientists: "If you only need to compute a specific type of function, you can design your communication system to be much more efficient than sending the whole message, but less efficient than just checking for one specific ID."

The Takeaway

The authors created a mathematical map showing exactly how much "data" you can compress based on the "complexity" of the question you want to answer.

Simple, rare questions = You can send huge amounts of data.
Complex, common questions = You are limited to standard data rates.
Everything in between = You get a customized data rate that scales in fascinating new ways (like $n^2$ or $n \log n$ ).

It's like realizing that if you only need to know if a storm is coming, you don't need a weather report for the whole planet; you just need a specific sensor reading. And depending on which sensor reading you need, you can send that information much faster than you thought possible.

1. Problem Formulation

The paper addresses the Boolean Function Computation (BFC) problem over noisy point-to-point communication channels.

Setup: A transmitter holds a binary message $i \in \{0, 1\}^m$ of length $m$ . It encodes this into a codeword $X^n$ of length $n$ and transmits it over a noisy channel $W$ .
Receiver's Goal: Unlike classical Shannon transmission (where the receiver must recover the full message $i$ ) or standard Identification (where the receiver checks if the message is a specific $i_0$ ), the receiver here aims to compute a Boolean function $f(i) \in \{0, 1\}$ .
Constraints:
- The function $f$ is chosen by the receiver from a known class of functions $\mathcal{F} \subseteq \{f: \{0, 1\}^m \to \{0, 1\}\}$ .
- The transmitter does not know which specific function $f$ the receiver will choose; it only knows the class $\mathcal{F}$ .
- The receiver must reliably decide whether $f(i) = 0$ or $f(i) = 1$ based on the channel output $Y^n$ .
Objective: Determine the asymptotic relationship between the message length $m$ and the channel uses $n$ such that reliable computation is possible. Specifically, the paper seeks the Computation Capacity, defined by the scaling behavior of $m$ as a function of $n$ .

2. Methodology and Characterization

The authors characterize the difficulty of the computation task based on the Hamming weight of the Boolean functions in the class $\mathcal{F}$ .

Hamming Weight ( $S$ ): Defined as the cardinality of the pre-image of 1, i.e., $S = |f^{-1}[1]|$ . This represents the number of input messages for which the function outputs 1.
Function Classes: The paper analyzes classes of functions where the Hamming weight is bounded or equal to a specific value $S$ , denoted as $\mathcal{F}_m(S)$ or $\mathcal{F}_m(\le S)$ .
Scaling Functions: The paper introduces a scaling function $L(R, n)$ $L (R, n)$ to describe how $m$ $m$ grows with $n$ $n$ .
- Linear scaling ( $m \sim Rn$ ) corresponds to Shannon transmission.
- Exponential scaling ( $m \sim 2^{Rn}$ ) corresponds to Identification.
- Intermediate scalings (polynomial, sub-exponential, quasi-linear) are explored for intermediate Hamming weights.

3. Key Contributions

The paper makes three primary contributions:

Generalization of Identification: It formalizes BFC as a generalization of the "Identification via Channels" problem introduced by Ahlswede and Dueck. It shows that Identification is a special case of BFC where the Hamming weight $S=1$ .
Computation Capacity Characterization: It derives tight achievability and converse bounds for the computation rate across six distinct regimes of Hamming weight $S$ .
Unified Framework: It connects BFC to semantic communication and propositional logic, demonstrating that computing a Boolean function is equivalent to evaluating the semantics of a logical formula given a truth assignment.

4. Main Results

The results are summarized in Table I of the paper. Let $C$ be the Shannon capacity of the channel. The achievable computation rate and the scaling of $m$ depend on the Hamming weight $S$ :

Case	Hamming Weight $S$	Scaling of $m$ (w.r.t $n$ )	Achievable Rate / Capacity
1	Constant ( $S = c$ )	Exponential ( $m \sim 2^{Cn}$ )	Rate $C$ (Matches Identification)
2	Polynomial ( $S = c m^\beta$ )	Exponential ( $m \sim 2^{\frac{C}{1+2\beta}n}$ )	Rate $\frac{C}{1+2\beta}$
3	Log-Polynomial ( $S = c m \log m$ )	Sub-exponential ( $m \sim 2^{\sqrt{C/2}\sqrt{n}}$ )	Rate $\sqrt{C/2}$
4	Super-Polynomial ( $S = c 2^{m^{1/b}}$ )	Polynomial ( $m \sim n^b$ )	Rate $\frac{C}{3(\lfloor 3/C+1 \rfloor)^{b-1}}$
5	Near-Exponential ( $S = c 2^{m/\log m}$ )	Quasi-linear ( $m \sim n \log n$ )	Rate $C/2$
6	Exponential ( $S = c 2^{\gamma m}$ )	Linear ( $m \sim \frac{C}{\gamma} n$ )	Rate $C/\gamma$ (Matches Shannon)

Tightness: For all cases, the achievability and converse results match in terms of the scaling behavior (e.g., both are exponential, or both are linear), even if the exact leading coefficients differ slightly in some regimes.
Transition: The results demonstrate a smooth transition from the "Identification regime" (where $m$ can be exponentially large) to the "Shannon transmission regime" (where $m$ scales linearly) as the Hamming weight $S$ increases from constant to exponential.

5. Technical Approach

Achievability (Direct Part):
- The authors construct codes using a stochastic encoder that maps messages to subsets of a standard channel codebook.
- They utilize a combinatorial result (Proposition 1, modified from Ahlswede & Dueck) to ensure that the subsets corresponding to different messages have small overlaps.
- The decoder constructs a decision region based on the union of codewords corresponding to the pre-image of 1 for the target function.
- Error analysis involves bounding the probability of "false negatives" (missing a 1) and "false positives" (detecting a 1 when it is 0), showing that errors vanish as $n \to \infty$ for the derived scaling laws.
Converse (Upper Bound):
- The authors prove that any BFC code for a class $\mathcal{F}$ can be converted into a standard Identification (ID) code.
- They construct a subset of functions within $\mathcal{F}$ that have low overlap in their pre-images (using a Gilbert-type bound for constant weight sequences).
- By applying the known converse bounds for Identification codes (which limit the number of identifiable messages to $2^{2^{nC}}$ ), they derive upper bounds on $m$ for the BFC problem.

6. Significance

Bridging Communication Paradigms: The paper unifies two major paradigms in information theory: Shannon Transmission (recovering the whole message) and Identification (checking a specific message). It reveals a continuum of capabilities based on the "complexity" (Hamming weight) of the function to be computed.
Semantic Communication: The work provides a rigorous information-theoretic foundation for semantic communication, where the goal is to transmit the "meaning" (the result of a function) rather than the raw data. It quantifies how much more efficient communication can be when the receiver only needs a specific property of the data.
Practical Implications: The results suggest that for tasks like anomaly detection (e.g., "Is the battery voltage too high?"), where the function has a small Hamming weight, one can support significantly larger message spaces (exponential in $n$ ) compared to standard transmission, without increasing channel usage. Conversely, for complex functions (large Hamming weight), the system reverts to standard transmission limits.

In summary, this paper establishes the fundamental limits of computing Boolean functions over noisy channels, demonstrating that the "cost" of computation is intrinsically linked to the sparsity (Hamming weight) of the function's output distribution.