CS Paper Radar

Counterexample to a Proposed Capacity Characterization of the Relay Channel

Chun Hei Michael Shiu

cs.IT ·submitted 2026-09-16 14:27 UTC · v1

Abstract

We present a counterexample to the relay channel capacity characterization proposed in a recent work, which is based on properties of typical sequences. The counterexample uses a binary relay channel with a noiseless source-destination component and binary symmetric relay links. An achievable scheme exceeds the proposed capacity characterization, thereby disproving the characterization of the capacity for general relay channels. We highlight that the counterexample is obtained with the assistance of ChatGPT-6 Astra and the proofs are simplified with human effort.

Comment
10 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

The Capacity of the Relay Channel

cs.IT ·2026-09-14 ·Jonathan Ponniah
similarity 0.81
Abstract

The capacity of the relay channel is characterized by three schemes: decode-forward, coordinated compress-forward, and uncoordinated compress-forward. The proof relies entirely on properties of typical sequences.

0.30

An Improved Upper Bound on the Capacity of the Primitive Diamond Relay Channel

cs.IT ·2026-10-08 ·Deniz Gündüz, Yanxiao Liu, Yi Liu
theory similarity 0.68
Abstract

We study the capacity of the primitive diamond relay channel and derive an improved upper bound compared with existing upper bounds by employing the Csiszár--Körner--Marton sum identity and Gallager-type identification. For Gaussian primitive diamond relay channels, we show that our proposed bound coincides with the existing strengthened Gaussian upper bound of Wu, Özgür, Peleg, and Shamai. For discrete memoryless channels, our bound can be strictly tighter than both the cut-set bound and the existing upper bound, and we assess the improvement using different channel instances, together with a decode--forward/compress--forward time-sharing inner bound.

0.22

Can Quantum Entanglement Increase the Capacity of a Classical Relay Channel?

cs.IT quant-ph ·2026-10-18 ·Elsa Mizrahi, Uzi Pereg
theory similarity 0.60
Abstract

We show positive and negative results on classical relay channels with entanglement assistance, revealing a sharp contrast between strictly causal and causal relay encoding. First, we consider van der Meulen's setting of a unit-delay relay, with strictly causal encoding. We show that the standard cutset upper bound continues to hold with entanglement assistance, and deduce that entanglement does not increase the capacity for several classes of relay channels. Second, we consider a zero-delay relay, where the encoding is causal. We present an example in which entanglement enables rates that exceed the cutset upper bound by at least 12.5%. Namely, entanglement shared between the source and relay significantly increases the capacity of a classical zero-delay relay channel.

0.14

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.59
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.42

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.57
Abstract · A part of this work has been reported in https://arxiv.org/pdf/2601.12640

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. In this paper, we formulate the notion of computation capacity, and derive achievability and converse results for a large class of functions $F$, characterized by the Hamming weight of functions. Different from the classical transmission problem, the performance of the function computation problem is jointly characterized by the computation capacity and the rate function, namely how $m$ scales with $n$ asymptotically. Our results give a complete characterization of the rate function of the computation problem, and provide upper and lower bounds on the computation capacity, where they differ by a factor of at most $2$.

0.52

Rate Optimal Streaming Codes Under an Extended Delay Profile for Three-Node Relay Networks

cs.IT ·2026-11-13 ·Ke Wang, Wenjie Ma, Zhipeng Li, Yaqiang Zhang
theory similarity 0.55
Abstract · 27 pages

We study streaming codes for a three-node relay network with burst lengths $b_1,b_2$ and an end-to-end decoding delay $T$. Let $u=\max\{b_1,b_2\}$ and $v=\min\{b_1,b_2\}$, and write $T-v=pu+q$, where $T\ge u+v$ and $0\le q<u$. We develop two binary constructions, SR and SR-2, using extended delay profiles that allow the relay to forward causally invertible combinations of current and past source symbols. The SR construction attains the non-adaptive rate upper bound whenever \[ \frac{T-u-v}{2u-v}\le\left\lfloor\frac{T-u-v}{u}\right\rfloor. \] SR-2 enlarges this range under the sufficient condition \[ q(v-q)\le(p-1)u(u-v). \] These constructions complement the known divisibility and large-delay regimes. We also establish two limitations of systematic ordinary coordinate forwarding. First, it cannot attain the rate upper bound when $0<T-u-v<v$. Second, for equal burst lengths $b$, it attains the bound if and only if $b\mid(T-2b)$; a quantitative upper bound gives a strictly positive rate gap in every nondivisible case. These converses allow nonlinear components and predetermined time variation within the stated ordinary-forwarding architecture. Existing adaptive schemes for equal bursts approach the same rate upper bound asymptotically using time-varying convolutional codes and lie outside the non-adaptive setting considered here.

0.27

When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions

cs.IT ·2026-10-21 ·Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh
theory similarity 0.55
Abstract

We consider the problem of binary sequence reconstruction where a sequence is transmitted multiple times over a channel, and each undergoes substitution errors by an arbitrary error vector of Hamming weight exactly $t$. We determine $N_{\mathrm{wc}}$, the minimum number of distinct channel output observations guaranteeing unique reconstruction by an optimal decoder, and show that the bit-wise majority-vote decoder, which was proved by Levenshtein (2001) to be optimal for channels corrupting up to $t$ bits, is in fact suboptimal here. Despite this suboptimality, we prove a condition that admits a practical early-termination rule, necessary for every decoder at any number of outputs $N$, and sufficient for bit-wise majority-vote even below $N_{\mathrm{wc}}$. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below $N_{\mathrm{wc}}$ when the block-length $k>2t+1$. Finally, we propose an alternative algorithm aimed at guaranteeing unique reconstruction with fewer observations than bit-wise majority-vote, and demonstrate through exhaustive enumeration that it successfully decodes channel output-sets where bit-wise majority-vote fails.

0.11

Channel dichotomies

cs.IT quant-ph ·2026-10-30 ·Aadil Oufkir, Mario Berta
similarity 0.54
Abstract · 34 pages, 4 figures

We study channel interconversion under non-signalling superchannels, where the asymptotic conversion rate is given by the ratio of the channel capacities. Our main result determines the second-order expansion of the optimal target length. Namely, when each channel has a single capacity-achieving dispersion, the coefficient is given by the inverse sesquinormal distribution, with parameters determined by the capacities and dispersions. The result extends state-dichotomy theory to channels: one superchannel approximates the target uniformly over inputs and maps every reference channel whose output is independent of its input to another such channel. As in state dichotomies, there are finite-error resonances where the second-order term vanishes, leaving an $O(\log n)$ remainder. Crucially, our new characterization cannot be obtained by concatenating channel coding and simulation protocols [Cao {\it et al.}~IEEE Trans.~Inf.~Theory (2024)]. Instead, the proof combines comparisons of binary hypothesis testing experiments with uniform Gaussian estimates and a construction that uses symmetry within type classes to satisfy the non-signalling constraints. Shared randomness assistance already suffices at first order, but we show that its second-order behaviour can differ strictly from the non-signalling case.

0.17