When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions
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 Nwc, 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 Nwc. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below Nwc 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.
Related
- The differentiation and integration operator on weighted spaces of analytic functions in the weight sequence setting
- Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
- Degree Sequence Reconstruction from Subgraph Traces
- On Sequence Reconstruction Problem for q-ary Deletion Channels
- The majority of a cactus is prickly
BibTeX
@misc{papadopoulou2026when,
title = {{When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions}},
author = {Vivian Papadopoulou and Yonatan Yehezkeally and V. Arvind Rameshwar and Antonia Wachter-Zeh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30001},
eprint = {2610.30001},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30001},
}
RIS
TY - UNPB
TI - When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions
AU - Vivian Papadopoulou
AU - Yonatan Yehezkeally
AU - V. Arvind Rameshwar
AU - Antonia Wachter-Zeh
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30001
UR - https://arxiv.org/abs/2610.30001
AB - 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_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_wc. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below N_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.
ER -