CS Paper Radar

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

Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh

cs.IT ·submitted 2026-10-21 16:37 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.68
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

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.67
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.43

Universal Decoding for Unequal Error Protection

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Albert Guillén i Fàbregas
similarity 0.66
Abstract

We study universal unequal error protection of a single special message over discrete memoryless channels. We construct a sequence of codes with a decoding rule that does not depend on the channel transition law. We derive an achievable error exponent for the special message while ensuring reliable decoding of the ordinary messages. The resulting exponent strictly improves on the natural equal-error-protection random-coding baseline and remains positive as the rate approaches capacity. For symmetric channels, it converges to the optimal red-alert exponent at capacity.

0.17

Diagnosing the Refuted Mismatched Decoding Converse for Binary-Input Channels

cs.IT ·2026-09-23 ·Jonathan Scarlett
theory similarity 0.66
Abstract · This work is AI-assisted, and a full declaration is given at the end of the paper

We revisit the claimed converse theorem for mismatched decoding over binary-input discrete memoryless channels (Balakirsky, 1995) and the subsequent work refuting this converse via a numerical counter-example (Scarlett, Somekh-Baruch, Martinez, and Guillén i Fàbregas, 2015). A notable gap in the existing understanding is that no concrete flaw was identified in Balakirsky's analysis. In this paper, Balakirsky's proof is "diagnosed", and it is demonstrated that (i) his permutation lemma is flawed regardless of the correctness of his combinatorial approximation lemma; (ii) there are at least two specific incorrect steps regarding restricted codes and selector sequences, and these appear to be unlikely to admit a local repair; and (iii) the proposition in which these incorrect steps are used is false in general.

0.19

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.65
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22

A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding

cs.IT ·2026-10-28 ·Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
theory similarity 0.64
Abstract

We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.

0.47

Thermodynamic characterization of message-passing: Framework and initial study

cs.IT cond-mat.stat-mech ·2026-10-26 ·Kalana G. Abeywardena, Stark C. Draper
publishedtheory similarity 0.63
Abstract · Published in IEEE Journal on Selected Areas in Information Theory (JSAIT), August 2026. 36 pages, 10 figures

We study the thermodynamic efficiency of message-passing decoders using the mismatch cost framework. This framework quantifies the excess entropy generated when a system operates away from the thermodynamically optimal initial distribution. It provides a computable lower bound on irrecoverable energy loss. The decoder is modeled as a main decoding program with local message updates implemented as subroutines. Memory is treated as an external copying subsystem whose thermodynamic cost is excluded. Studying the $[7,4]$ Hamming code transmitted over a binary erasure channel, we show how the channel-induced initialization statistics and the step-wise evolution of the algorithmic state distribution during decoding determine the total mismatch cost. We further show that different thermodynamically optimal state distributions, representing different underlying physical implementations of the decoder, can produce different thermodynamic costs for identical decoding dynamics. Conditioning the input distribution on correctable and non-correctable erasure patterns further reveals distinct thermodynamic signatures. These results demonstrate that thermodynamic cost is jointly governed by decoding dynamics, input statistics, and hardware characteristics. This points to opportunities for thermodynamically-informed decoder design to realize energy-efficient physical implementations.

0.59

Task-Oriented Boolean Function Computation: Practical Code Constructions

cs.IT ·2026-10-01 ·Yangshuo He, Guanding Yu, Jingge Zhu
similarity 0.63
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 $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.

0.07