pith. sign in

arxiv: 2601.12640 · v2 · submitted 2026-01-19 · 💻 cs.IT · math.IT

Beyond Identification: Computing Boolean Functions via Channels

Jingge Zhu , Matthias Frey This is my paper

Pith reviewed 2026-05-16 13:48 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords computation capacityBoolean functionschannel codingidentification via channelsHamming weight
0
0 comments X

The pith

Computation capacity for recovering unknown Boolean functions over channels is characterized by the Hamming weight of the function class.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines computation capacity as the largest asymptotic growth rate of message length m relative to codeword length n such that a receiver can reliably recover the value of a Boolean function chosen from a known class F. The transmitter does not know which function in F will be queried, generalizing the identification problem to one of functional computation. For function classes grouped by Hamming weight the authors derive matching achievability and converse bounds that are tight in scaling behavior. This framework shows how channel resources can be allocated to support reliable computation rather than full message recovery.

Core claim

The central claim is that a computation capacity exists for the problem of recovering an unknown Boolean function from class F over a memoryless channel, and that this capacity admits explicit characterization in terms of scaling laws between m and n when F is partitioned according to the Hamming weight of its members.

What carries the argument

Computation capacity, the supremum rate at which message length m can grow with transmission length n while permitting reliable recovery of the Boolean function value.

If this is right

  • For every Hamming-weight class considered, the scaling relation between m and n is tight.
  • The same capacity characterization applies to all functions within each fixed-weight class.
  • The results hold for any memoryless channel under the standard asymptotic regime.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The framework may extend to settings where multiple receivers each need a different function of the same message.
  • Non-asymptotic finite-length versions of the same problem could be studied by replacing the scaling limits with explicit error exponents.
  • Connections may exist to functional compression problems in which only a Boolean outcome must be reproduced.

Load-bearing premise

The Boolean function is known to belong to a class F whose Hamming-weight structure permits explicit capacity bounds under standard memoryless channel models and asymptotic block lengths.

What would settle it

A concrete counterexample would be any specific Hamming-weight class for which the largest achievable m fails to scale exactly as predicted by the derived upper and lower bounds.

read the original abstract

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. We formulate the notion of computation capacity, and derive achievability and converse results for selected classes of functions $F$, characterized by the Hamming weight of functions. Our obtained results are tight in the sense of the scaling behavior for all cases of $F$ considered in the paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces computation capacity for a point-to-point memoryless channel in which a transmitter encodes a length-m binary message into a length-n codeword and the receiver must recover the value of a Boolean function of the message, where the function is drawn from a known class F parameterized by Hamming weight. Achievability and converse bounds are derived via reduction to a generalized identification problem, random coding for the direct part, and a Fano-type inequality with single-letterization for the converse; the bounds are claimed to match in scaling for every weight class examined.

Significance. If the derivations are correct, the work meaningfully extends the Ahlswede-Dueck identification capacity framework to a natural class of computation tasks. The explicit scaling characterizations for Hamming-weight classes supply concrete, falsifiable predictions about the m-vs-n tradeoff that can be checked against standard random-coding arguments.

minor comments (3)
  1. [§2] §2 (Definition of computation capacity): the precise error criterion (average vs. worst-case over F) should be stated explicitly, as it affects whether the converse applies uniformly or only in expectation.
  2. [§4] §4 (Converse): the single-letterization step relies on the fixed structure of F; a brief remark on why the auxiliary random variable remains independent of the particular weight class would improve readability.
  3. [Table 1] Table 1 or equivalent summary: the scaling exponents for each Hamming-weight regime should be listed side-by-side with the corresponding identification-capacity baseline for direct comparison.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The provided summary accurately reflects the paper's contributions on computation capacity for Boolean functions over channels, including the generalization of the Ahlswede-Dueck identification framework and the tight scaling results for Hamming-weight classes.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper defines computation capacity for recovering a Boolean function from a known class F (parameterized by Hamming weight) over a memoryless channel. Achievability proceeds via random coding arguments that generalize the Ahlswede-Dueck identification framework, while the converse applies Fano-type inequalities and single-letterization. These steps rely only on standard asymptotic information-theoretic tools, the fixed structure of F, and the usual block-length regime; no parameter is fitted to a subset of results and then renamed as a prediction, and no load-bearing premise reduces to a self-citation or self-definitional loop. The claimed tightness in scaling behavior is obtained by matching independently derived bounds rather than by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard information-theoretic assumptions about memoryless channels and asymptotic regimes; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The underlying channel is memoryless and the analysis is in the asymptotic block-length regime.
    Standard modeling assumption invoked for capacity derivations in communication theory.

pith-pipeline@v0.9.0 · 5446 in / 1155 out tokens · 36423 ms · 2026-05-16T13:48:22.095225+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Identification via channels,

    R. Ahlswede and G. Dueck, “Identification via channels,”IEEE Transactions on Information Theory, vol. 35, no. 1, pp. 15–29, Jan. 1989, conference Name: IEEE Transactions on Information Theory

    work page 1989

  2. [2]

    Identification in the presence of feedback-a discovery of new capacity formulas,

    ——, “Identification in the presence of feedback-a discovery of new capacity formulas,”IEEE Transactions on Information Theory, vol. 35, no. 1, pp. 30–36, Jan. 1989

    work page 1989

  3. [3]

    Deterministic Identification Over Channels With Power Constraints,

    M. J. Salariseddigh, U. Pereg, H. Boche, and C. Deppe, “Deterministic Identification Over Channels With Power Constraints,”IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 1–24, Jan. 2022

    work page 2022

  4. [4]

    Deterministic Identification Over Channels With Finite Output: A Dimensional Perspective on Superlinear Rates,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Deterministic Identification Over Channels With Finite Output: A Dimensional Perspective on Superlinear Rates,”IEEE Transactions on Information Theory, vol. 71, no. 5, pp. 3373–3396, May 2025

    work page 2025

  5. [5]

    Explicit construction of optimal constant-weight codes for identification via channels,

    S. Verdu and V . Wei, “Explicit construction of optimal constant-weight codes for identification via channels,”IEEE Transactions on Information Theory, vol. 39, no. 1, pp. 30–36, Jan. 1993

    work page 1993

  6. [6]

    On identification via multiway channels with feedback,

    R. Ahlswede and B. Verboven, “On identification via multiway channels with feedback,”IEEE Transactions on Information Theory, vol. 37, no. 6, pp. 1519–1526, Nov. 1991

    work page 1991

  7. [7]

    Strongly universal hashing and identification codes via channels,

    K. Kurosawa and T. Yoshida, “Strongly universal hashing and identification codes via channels,”IEEE Transactions on Information Theory, vol. 45, no. 6, pp. 2091–2095, Sep. 1999

    work page 2091

  8. [8]

    Code Constructions and Bounds for Identification via Channels,

    O. G ¨unl¨u, J. Kliewer, R. F. Schaefer, and V . Sidorenko, “Code Constructions and Bounds for Identification via Channels,”IEEE Transactions on Communications, vol. 70, no. 3, pp. 1486–1496, Mar. 2022

    work page 2022

  9. [9]

    General theory of information transfer: Updated,

    R. Ahlswede, “General theory of information transfer: Updated,”Discrete Applied Mathematics, vol. 156, no. 9, pp. 1348–1388, May 2008

    work page 2008

  10. [10]

    Identification via the Broadcast Channel,

    A. Bracher and A. Lapidoth, “Identification via the Broadcast Channel,”IEEE Transactions on Information Theory, vol. 63, no. 6, pp. 3480–3501, Jun. 2017

    work page 2017

  11. [11]

    Codes for Identification via Channels: Tutorial for Communications Generalists,

    C. von Lengerke, J. A. Cabrera, M. Reisslein, and F. H. Fitzek, “Codes for Identification via Channels: Tutorial for Communications Generalists,”IEEE Communications Surveys & Tutorials, pp. 1–1, 2025

    work page 2025

  12. [12]

    H. B. Enderton,A Mathematical Introduction to Logic. Academic Press, 1972

    work page 1972

  13. [13]

    Strong converse for identification via quantum channels,

    R. Ahlswede and A. Winter, “Strong converse for identification via quantum channels,”IEEE Transactions on Information Theory, vol. 48, no. 3, pp. 569–579, Mar. 2002

    work page 2002

  14. [14]

    Lower bounds for constant weight codes,

    R. Graham and N. Sloane, “Lower bounds for constant weight codes,”IEEE Transactions on Information Theory, vol. 26, no. 1, pp. 37–43, Jan. 1980

    work page 1980