Capacity regimes for Boolean function computation via channels

=== DRAFT ===

Technical Summary: Capacity Regimes for Boolean Function Computation via Channels

Problem Formulation
This paper addresses the problem of computing Boolean functions over noisy point-to-point communication channels. In this framework, a transmitter holds a binary message $i$ of length $m$ and encodes it into a codeword $X^n$ of length $n$ for transmission. Unlike classical Shannon transmission, where the receiver must recover the full message $i$, the receiver's goal here is to recover the value of a specific Boolean function $f(i)$, where $f: \{0, 1\}^m \to \{0, 1\}$. Crucially, the function $f$ is chosen by the receiver from a known class of functions $\mathcal{F}$ but is unknown to the transmitter at the time of encoding. The receiver must reliably decide whether $f(i) = 0$ or $f(i) = 1$ based on the channel output $Y^n$.

This problem generalizes the "identification via channels" framework introduced by Ahlswede and Dueck. In the identification problem, the decoder determines if the transmitted message is a specific one; this corresponds to a Boolean function computation problem where the function class consists of indicator functions for single messages (Hamming weight $S=1$). The paper investigates the asymptotic relationship between the message length $m$ and the channel use length $n$: given $n$, how large can $m$ be such that the Boolean function value can be recovered reliably?

Methodology and Definitions
The authors define a Boolean Function Computation (BFC) code consisting of an encoder (a probability distribution over codewords for each message) and a decoder (a set of decoding regions for each function in $\mathcal{F}$). Performance is measured by false positive and false negative error probabilities.

The core of the analysis relies on the Hamming weight of the Boolean functions, defined as the cardinality of the pre-image of 1, denoted $S(m) = |f^{-1}[1]|$. The paper focuses on two classes of functions:

1. $\mathcal{F}_m(S)$: Functions with Hamming weight exactly equal to $S$.
2. $\mathcal{F}_m(\le S)$: Functions with Hamming weight less than or equal to $S$.

The authors introduce the concept of computation capacity and a rate function $L(R, n)$, which describes how $m$ scales with $n$ (e.g., $m \sim n$ for linear scaling, $m \sim 2^n$ for exponential scaling). The analysis distinguishes between valid and equivalent rate functions to handle asymptotic behaviors rigorously.

Key Contributions and Results
The primary contribution is a complete characterization of the computation capacity and the scaling laws of $m$ with respect to $n$ for the BFC problem, categorized by the growth rate of the Hamming weight $S(m)$. The results are divided into three regimes:

1. Small $S(m)$ Regime:

   • Condition: $\log S(m) = O(\log m)$ (e.g., $S(m)$ is constant or polylogarithmic in $m$).
   • Result: The message length $m$ can scale exponentially with $n$ ($m \sim 2^{nR}$).
   • Capacity: The computation capacity is $C$ (the Shannon capacity of the channel) with the rate function $L(R, n) = 2^{nR}$. This recovers the double-exponential scaling known in the identification problem ($S=1$).

2. Medium $S(m)$ Regime:

   • Condition: $\log S(m) = \omega(\log m)$ but $\log S(m) \le \alpha m$ for some $\alpha \in (0, 1)$.
   • Result: The scaling of $m$ depends on the specific form of $S(m)$. It can be sub-exponential, polynomial, or quasi-linear.
   • Capacity: The computation capacity lies within $[C/2, C]$. The exact rate function is characterized as $L(R, n) = S^{-1}(2^{nR})$, where $S^{-1}$ is the inverse of the weight function.
   • Examples:
     • If $S(m) = c m^\beta$, $m$ scales as $2^{n \frac{C}{1+2\beta}}$.
     • If $S(m) = c 2^{m/b}$, $m$ scales as $(nR)^b$.
     • If $S(m) = c 2^{m/\log m}$, $m$ scales as $n \log n$.

3. Large $S(m)$ Regime:

   • Condition: $\log S(m) / m \to 1$ (i.e., $S(m)$ is close to $2^m$).
   • Result: The message length $m$ scales linearly with $n$ ($m \sim nR$).
   • Capacity: The computation capacity is exactly $C$ with the rate function $L(R, n) = nR$. This behavior matches the classical Shannon transmission problem.
   • Note: Due to symmetry, the results for $\mathcal{F}_m(S)$ are symmetric around $S = 2^{m-1}$. For the class $\mathcal{F}_m(\le S)$, the linear scaling holds for all $S \ge 2^{m-1}$.

Bounds and Tightness
The paper provides achievability and converse results that bound the computation capacity. For all regimes, the derived upper and lower bounds on the capacity differ by a factor of at most 2. In specific cases (such as the small and large regimes), the capacity is shown to be exactly the Shannon capacity $C$.

Significance
The paper claims to provide a complete characterization of the rate function for Boolean function computation, bridging the gap between the identification problem (exponential scaling) and the classical transmission problem (linear scaling). It demonstrates that the communication efficiency of the BFC code is fundamentally determined by the Hamming weight of the function class. The results unify previous scattered findings on identification, ranking, and bit-identification problems under a single theoretical framework, showing how the "complexity" of the function (measured by its weight) dictates the trade-off between message length and channel uses. The work establishes that while the receiver does not need to recover the full message, the ability to compute a function with high weight essentially forces the system to behave like a standard transmission channel, whereas low-weight functions allow for significantly higher message rates.