Task-Oriented Boolean Function Computation: Practical Code Constructions
Abstract
Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of 1/2. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate Rc, this construction achieves an asymptotic computation rate of Rc/2, yielding C/2 when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of 10−5 for the exact-weight and rank-test tasks, respectively.
Related
- Exact volume computation for Boolean quadric polytopes of series-parallel graphs
- Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
- On the most informative Boolean function under noise
- An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
- Almost every Boolean function has central threshold degree
BibTeX
@misc{he2026taskoriented,
title = {{Task-Oriented Boolean Function Computation: Practical Code Constructions}},
author = {Yangshuo He and Guanding Yu and Jingge Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01228},
eprint = {2610.01228},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01228},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Task-Oriented Boolean Function Computation: Practical Code Constructions
AU - Yangshuo He
AU - Guanding Yu
AU - Jingge Zhu
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.01228
UR - https://arxiv.org/abs/2610.01228
AB - Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of 1/2. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate R_c, this construction achieves an asymptotic computation rate of R_c/2, yielding C/2 when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of 10^−5 for the exact-weight and rank-test tasks, respectively.
ER -