Information Theory
Statistical Dark Matter: Synergy is everywhere but is hard to capture
Alberto Liardi, Fernando E. Rosas, Daniele Marinazzo et al. (+3 more)
The information-theoretic construct of synergy refers to the statistical structure that is contained in three or more variables, but not in any subset of them. Here we leverage recent advances in multivariate information theory to show that synergy is far more prevalent in complex systems than previously thought. In particular, we show that many-body systems tend to become strongly dominated by synergy as the number of subcomponents grows. At the same time, our results also reveal that commonly used tools for statistical modelling severely underestimate synergistic structures. These findings imply that synergy constitutes a prevalent, yet often invisible, informational component of complex systems. With a certain poetic licence, we interpret these results as suggesting that synergy is the dark matter of statistics - interdependencies that we know exist, but standard instruments fail to detect.
Read the full abstract ▾
All authors Alberto Liardi, Fernando E. Rosas, Daniele Marinazzo, Thomas F. Varley, Michael Gastpar, Pedro A.M. Mediano
Information Theory
Quaternary Preparata codes are quasi-perfect covering codes in the Hamming metric
Tamal Maharaj
The quaternary Preparata codes of Hammons, Kumar, Calderbank, Sloane and Solé are $\mathbb{Z}_4$-linear codes of length $2^m$ with $4^{2^m-m-1}$ codewords. They are usually studied through their binary Gray images, that is, in the Lee metric. We consider them instead as codes over a 4-letter alphabet with the Hamming metric. We show that for odd $m$ they have covering radius 2 and minimum distance 4, so they are quasi-perfect. For even $m$ the same construction has covering radius 3. The proof is a short computation with Teichmüller representatives in the Galois ring $\mathrm{GR}(4,m)$, and it also gives the coset weight distribution. The covering density of these codes tends to $9/8$. The best previously known infinite families of quaternary codes with covering radius 2 have covering density about 1.5. Consequently $K_4(n,2)\le 4^{n-m-1}$ for all $n\ge 2^m$ and odd $m$, which improves the best available bounds for a range of lengths above each $2^m$. For $m=3$ the code is the octacode, and it gives $K_4(8,2)\le 256$; the previous bound was 352, from 2005, and the best lower bound is 251. We also give a quaternary code showing $K_4(6,2)\le 48$, where the previous bound was 52, together with consequences for larger alphabets.
Read the full abstract ▾
Information Theory
SymNetPro: LOS-Aware Directional Multi-Transmitter Localization from Sparse Radio Observations
Lyuzhou Ye, Heng Fan and Yan Huang
Directional multi-transmitter localization from sparse received-power observations is difficult because the receiver observes only the source-unresolved aggregate field: multiple directional sources superpose, building blockage fragments their visible regions, and stronger sources can mask weaker ones. We present SymNetPro, which retains the dual-task
radio-map reconstruction and localization backbone of SymNet and adds two targeted components. First, a sparse line-of-sight (LOS)-aware
attention bias injects obstruction-aware spatial relations into selected
token interactions. Second, transmitter-drop augmentation recomposes training scenes after removing one sample-supported transmitter, exposing the model to controlled source-cardinality variation. Experiments on directional ray-traced urban environments show substantially lower OSPA than representative localization baselines under extreme sparse sampling, with consistent gains under measurement noise and increasing transmitter count. A transmitter-specific evidence analysis further shows that remaining misses concentrate in regimes where the target contributes little distinguishable power to the aggregate observation.
Read the full abstract ▾
Information Theory
Soft-Output GRAND-Aided Macrosymbol
Sarah Khalifeh, Alexander Mariona, Ken R. Duffy et al. (+1 more)
Guessing Random Additive Noise Decoding-Aided Macrosymbol (GRAND-AM) provides a coding-based solution for non-orthogonal multiple access (NOMA) systems, enabling joint multiuser detection and error correction. GRAND-AM outperforms prior methods in symbol error rates while providing hard-detection output. We introduce soft-output GRAND-AM (SOGRAND-AM), a macrosymbol-level joint multiuser detection and decoding framework which generates calibrated bitwise a posteriori error probabilities. SOGRAND-AM extends GRAND-AM by enabling soft-decision outer forward error correction decoders, transparently integrating with existing decoders. SOGRAND-AM achieves approximately 2 dB improvement in bit error rate at the output of the outer soft-input decoder compared to hard input with GRAND-AM.
Read the full abstract ▾
All authors Sarah Khalifeh, Alexander Mariona, Ken R. Duffy, Muriel Medard
Information Theory
Concurrent Coded Signal-Multiplexing Ranging for Half-Duplex Asynchronous Networks
Zijian Zhang and Yuan Shen
Signal-multiplexing network ranging (SM-NR) shares broadcasts across node pairs, but its sequential operation leads to a ranging cycle that grows linearly with network size. This paper proposes a concurrent coded SM-NR (CC-SM-NR) framework for asynchronous half-duplex networks. Firstly, the CC-SM-NR protocol coordinates concurrent transmissions through binary transmit-listen codewords. The transmit-listen schedule defined by these codewords ensures reciprocal observations subject to a finite concurrency limit. Then, we derive the exact minimum number of transmit-listen rounds without a concurrency limit, which reveals that the minimum grows logarithmically with network size. To account for practical scenarios, we establish the necessary and sufficient conditions for the constant-weight feasibility of codewords under a finite concurrency limit. Subsequently, we propose a low-complexity scheduling
algorithm that achieves the minimum round count within the constant-weight codeword class. To support higher observation redundancy, this scheduling design is extended through a greedy construction. Finally, simulation results demonstrate the effectiveness of the proposed schemes for network ranging.
Read the full abstract ▾
Information Theory
A proof of the Braun-Etzion-Vardy bound for binary subspace codes
Srikanth B. Pai
The notion of a linear subspace code in a projective space was introduced by Braun, Etzion and Vardy (2013), who conjectured that a linear subspace code in the projective space has at most 2^n codewords. We resolve this
conjecture. A novel character-theoretic argument is used to prove the
conjecture and the proof is self-contained.
Read the full abstract ▾
Information Theory
Non-Adaptive Learning of Sparse Erdős–Rényi Graphs via Affine Splitting
Hoang Ta
Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on $n$ vertices with at most $k$ edges, non-adaptive recovery requires $\Omega(\min\{k^2\log n,n^2\})$ queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdős–Rényi ($\mathrm{ER}$) graphs $G\sim \mathrm{ER}(n,q)$, with expected edge count $\bar{k}=q\binom{n}{2}$. Our scheme uses $O(\bar{k}\log n)$ queries and achieves exact recovery in $O(\bar{k}\log n)$ decoding time with probability tending to one throughout the regime $\bar{k}\to\infty$ and $\bar{k}=o(n^2)$. This improves the previous $O(\bar{k}^{1+\delta}\log n)$ decoding guarantee for any fixed $\delta>0$, while maintaining the same query order. The guarantee also extends beyond the previously studied regime $\bar{k}=\Theta(n^{2\theta})$ with fixed $\theta\in(0,1)$. Our approach builds on the binary splitting method used in prior work, which organizes vertices into a hierarchy of successively smaller groups. We introduce three main changes: (i) we use random affine hash functions over a finite field to process each candidate pair in constant time; (ii) we apply the splitting procedure directly to the full graph, avoiding the need to combine solutions to multiple smaller graph-learning subproblems; and (iii) we bound the total decoding workload directly rather than deriving separate high-probability bounds on candidate counts at each level.
Read the full abstract ▾
Information Theory · Cross-listed from cs.LG
Geometric Inductive Biases for Semi-Supervised Equalization: The Constellation-Aware Transformer
Avi Caciularu
Decoding signals over unknown channels with minimal pilot overhead is a critical challenge in next-generation communications. Existing deep learning approaches typically rely on generic encoders that struggle to model long-range temporal dependencies or efficiently capture the channel's physical properties from scarce data. We argue that standard architectures suffer from agnostic estimation gaps, as they must implicitly learn the constellation geometry that is already known. We introduce the Constellation-Aware
Transformer (CAT), a novel architecture that explicitly injects
geometric inductive biases into the equalization process. CAT is composed of a stack of custom TransFIRmer blocks, which use an "early interaction" paradigm to co-process received signals and ideal constellation symbols. Each block features a split Feed-Forward Network that applies a Finite Impulse Response (FIR)-inspired filter for deconvolution and a parallel MLP for
geometric refinement. We show that this design is structurally aligned with the optimal linear (
MIMO Wiener) receiver: its
attention can implement a matched-filter bank, and its bidirectional FIR branch provides the non-causal filtering that block MMSE equalization requires. In the semi-supervised setting, CAT needs fewer pilots than VAE and standard
Transformer baselines: on two of our three ISI channels, it reaches a lower SER with 64 pilots than they do with 128.
Read the full abstract ▾
Information Theory
A Continuous Projection Converse and a Weighted Construction for Uniquely Decodable Code Pairs
Lei Yu
We study the maximum sum rate of uniquely decodable code pairs. A weighted refinement of a complement-gluing construction yields an explicit code of length 672 and sum rate exceeding $1.318639029203$. An iterated projection argument, combined with a conditional
entropy estimate and a justified continuous limit, gives an upper bound of $1.480063425539$.
Read the full abstract ▾
Information Theory · Cross-listed from cs.LG
Short-Length Code Designs for Integrated Sensing and Communications: A Deep Learning Approach
Muah Kim, Shuangyang Li, Tayyebeh Jahani-Nezhad et al. (+2 more)
Integrated sensing and communication (
ISAC) enables joint communication and sensing using a shared waveform, but its signal design is challenging due to the inherent trade-off between the two objectives, particularly in the short blocklength regime. This paper proposes an autoencoder (AE)-based framework for
ISAC waveform design in noncoherent settings. We derive a modified Cramér-Rao bound for multi-target delay estimation and analyze the maximum-likelihood decoding rule for noncoherent communication under correlated fading. These results reveal structural connections and trade-offs between communication and sensing objectives in waveform design. Based on this analysis, the AE learns waveform representations that jointly optimize both functionalities, with a tunable parameter controlling the trade-off. Simulation results show that the proposed design outperforms conventional schemes in both communication reliability and sensing accuracy, especially under short blocklength and fading conditions.
Read the full abstract ▾
All authors Muah Kim, Shuangyang Li, Tayyebeh Jahani-Nezhad, Rafael F. Schaefer, Giuseppe Caire
Information Theory · Cross-listed from math.CO
Sunflowers of Reed–Solomon Codes
Roni Con, Anina Gruica, Maria Montanucci et al. (+1 more)
We introduce and study Reed–Solomon sunflowers, namely families of Reed–Solomon codes whose pairwise intersections are all equal to the same fixed subspace. This notion lies at the intersection of extremal subspace combinatorics and coding theory: it can be viewed as a structured version of the sunflower problem in the Grassmannian, and it naturally produces constant-dimension subspace codes with prescribed minimum distance. We focus mainly on the case in which the center is the one-dimensional space generated by the all-one vector. We give an algebraic criterion, expressed in terms of generalized $V$-
matrices, ensuring that a family of Reed–Solomon codes forms such a sunflower. We then study the size of these families through counting and constructions. In dimension two, we show that all distinct Reed–Solomon codes form a sunflower and determine its size by counting Reed–Solomon codes up to affine equivalence of their evaluation vectors. For fixed dimension $k\geq3$ and length $\ell\geq2k-1$, we give an explicit recursive construction with $\Omega_{k,\ell}(q^{\lfloor\ell/(2k-1)\rfloor})$ petals and a greedy existence argument with $\Omega_{k,\ell}(q^{\ell-2k+2})$ petals as $q\to\infty$. We also apply the greedy argument to obtain families of $[\ell,k]_q$ MDS codes of size $\Omega_{k,\ell}(q^{2(\ell-2k+2)})$, whose pairwise intersections have dimension at most one but need not be equal.
Read the full abstract ▾
All authors Roni Con, Anina Gruica, Maria Montanucci, Ferdinando Zullo
Information Theory · Cross-listed from cs.LG
The cost of useful natural gradient updates
Subhransu S. Bhattacharjee, Dylan Campbell and Rahul Shome
What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction $\varepsilon$ of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is $\Theta(\log(1/\delta)/(p\varepsilon^2))$ for small $\varepsilon$, where $p$ scales rare-state probabilities and $\delta$ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.
Read the full abstract ▾
Information Theory · Cross-listed from cs.LG
StarBOA: Real-Time Mamba State-Space Unrolling for Sparse Radar Micro-Doppler in ISAC Networks
Mustafa Bora Çelik, Ceren Çelik and Orhan Gazi
In Integrated Sensing and Communications (
ISAC), radar sensing must operate under chirp subsampling with up to 90% missing data. An
attention-based baseline, limited to a 52~ms buffer, collapses toward maximum uniform
entropy ($H=2.584$ bits) as sparsity increases, failing to capture long-range gait-cycle context. We propose StarBOA, which replaces
attention with a causal Mamba state-space model that updates incrementally on a per-window basis without re-scanning past reconstructions. By maintaining a persistent state, StarBOA integrates over $100\times$ more temporal history at no additional per-step computational cost. StarBOA outperforms the baseline's published results across all sparsity levels, with SSIM gains increasing from $+0.0379$ at 50% missing data to $+0.2472$ at 90%. Each window is processed in 1.53~ms with zero lookahead, demonstrating efficient causal reconstruction under extreme chirp subsampling.
Read the full abstract ▾
Information Theory
Geometry-Aware Multi-UAV Full-Duplex Communication: System Design and Experiment
Tao Yu, Kiyomichi Araki, Tomohiro Mogi et al. (+2 more)
The deployment of unmanned aerial vehicle (
UAV) systems relies on high-performance yet lightweight wireless links between
UAVs and ground stations (GSs). This paper presents a geometry-aware multi-
UAV in-band full-duplex (MU-IBFD) communication system that uses high-gain directional
antennas and separated uplink/downlink channels to convert self-interference into controllable co-channel interference (CCI) between
UAVs, thereby avoiding energy-intensive self-interference cancelers on
UAVs. We also derive a geometry-aware CCI model and define a reliable operating region (ROR) in the 3D airspace, within which the SINR requirement is satisfied. A prototype consisting of two
UAVs and a GS is developed, and field trials are conducted. The measured CCI as a function of
UAV positions agrees well with the theoretically predicted non-ROR region, and the downlink capacity significantly exceeds that of a conventional time-division duplex (TDD) with omni-directional scheme and higher transmit power and approaches that of ideal IBFD in most of the airspace. A proof-of-concept 4K/60p
video transmission further demonstrates the practical potential of the proposed MU-IBFD system.
Read the full abstract ▾
All authors Tao Yu, Kiyomichi Araki, Tomohiro Mogi, Yasushi Hada, Kei Sakaguchi