Peer Revenue Publish or profit

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Computer Science Information Theory

cs.IT Watch Information Theory (sign in to use)

Monday 28 September

Information Theory · Cross-listed from cs.RO

Memory in the Sky: Low-Altitude Question Answering with Multi-Agent Memory Aggregation

This paper studies low-altitude question answering (LAQA), in which distributed unmanned aerial vehicle (UAV) memories are aggregated at a ground server to answer questions about observations over a long horizon. Unlike conventional resource allocation based on sensing, communication, control, or computation metrics, LAQA requires an explicit measure of memory value. We propose a generative adversarial exam (GAE) that uses forward simulation to evaluate memory retrieval and exam scores to quantify memory quality. This enables the downstream QA value of candidate memories to be measured and optimized without accessing the internal mechanisms of the black-box captioning, retrieval, and reasoning pipeline. Building on this metric, we develop a memory-centric (MemCen) framework that jointly selects UAVs and allocates transmit power to maximize memory quality under communication constraints. In the noise-limited regime, we derive a QoM-aware capped water-filling law that explicitly connects task utility with physical-layer power allocation. We further develop penalty successive optimization (PSO) and learning to memorize (L2M) solvers. MemCen achieves QA accuracies of 92.4% and 84.0% in CARLA Town04 and Town05 under static and dynamic communication conditions, respectively. In real-world experiments, MemCen achieves 88.5% QA accuracy on the panoramic multi-agent system (PMAS) benchmark. Finally, UAV-to-robot-dog demonstrations further validate the practical utility of the acquired memories for environmental understanding and navigation.
Read the full abstract

All authors Chengyang Li, Yujie Wan, Shuai Wang, Kejiang Ye, Weijie Yuan, Boyu Zhou, Yik-Chung Wu, Chengzhong Xu, Huseyin Arslan

Information Theory · Cross-listed from eess.SP

Finite-Resolution Microwave Linear Analog Computer (MiLAC)-Aided Multiuser Beamforming

Large-scale antenna arrays are essential to future wireless networks but impose significant hardware and digital-processing burdens. The microwave linear analog computer (MiLAC) offers a promising architecture for addressing these challenges. In a MiLAC, beamforming is realized entirely in the analog domain through a reconfigurable multiport microwave network comprising tunable admittance elements. However, existing studies assume that these elements are continuously tunable, whereas practical implementations can support only finitely many configurable states. This paper investigates finite-resolution MiLAC-aided multiuser beamforming under lossless and reciprocal constraints with prescribed connectivity patterns. Each tunable susceptance is selected from a symmetric uniform finite-resolution codebook. We formulate an online problem that jointly optimizes the discrete susceptances and power allocation for a prescribed codebook, and an offline problem that designs the codebook based on channel statistics. By exploiting the odd-uniform codebook structure, we express each multilevel susceptance as a weighted sum of two-level variables and develop exact continuous penalty models for both the online beamforming and offline codebook design problems. We prove that, for sufficiently large penalty parameters, these penalty models are globally equivalent to their original discrete counterparts. Building on these formulations, we develop efficient ADMM-based algorithms for solving the two problems. Numerical results demonstrate that the performance of an unquantized fully-connected MiLAC can be approached with substantially reduced connectivity and finite resolution. In particular, a 3-bit stem-connected MiLAC achieves more than 95% of the sum-rate performance of the unquantized fully-connected MiLAC while requiring only 22% of its tunable components.
Read the full abstract

Information Theory

Improved bounds for constant-power and low-power error-correcting cooling codes

Low-power error-correcting cooling (LPECC) codes and constant-power error-correcting cooling (CPECC) codes provide error correction while controlling power consumption and thermal effects in on-chip buses. In this paper, we study binary CPECC and LPECC codes with \(e=w-3\). For CPECC codes, we extend the applicability of the upper bound previously obtained by Zhao and Zhang from the quadratic-order condition \(w\ge 2t(t+1)+2\) to \(w\ge w_0(t)\), where \(w_0(t)\sim \sqrt{2}\,t^{3/2}\). Using Steiner systems, we show that the CPECC bound is attainable and asymptotically tight for fixed \(t,w\). For LPECC codes, we establish the new upper bound \(\left\lfloor\frac{\binom{n+2}{3}}{\binom{w+t}{3}}\right\rfloor\) for \(w\ge \mu(t)\), where \(\mu(t)\sim \sqrt{2}\,t^{3/2}\). This bound is strictly smaller than the previous bound of Zhao and Zhang whenever both apply, and is asymptotically tight for fixed \(t,w\) in the stated range.
Read the full abstract

Information Theory

Large-Scale Autonomous Discovery of Kissing Number Constructions

The kissing-number problem is a classical problem in discrete geometry whose exact solution is known in only a few dimensions. Recent artificial-intelligence approaches have begun to discover improved configurations through large-scale numerical and combinatorial search, but converting such searches into general mathematical constructions and rigorous proofs remains challenging. Here we use Qiushi Engine, an autonomous multi-agent research system, to investigate kissing numbers and obtain new lower bounds in nineteen dimensions: $25$, $27$, $32$–$39$, $43$, $45$, and $49$–$55$. The resulting constructions arise from distinct structural mechanisms, including coordinated motions of contact layers, labelled direction reuse, joint support exchanges, signed-code replacements, cross-shell lattice constructions, low-overlap lattice isometries, and spherical-design moment certificates. They yield sharp capacities for parameterized signed-code models, deterministic image-union guarantees, and exact section and projection counts controlled by embedded root systems and anchor-graph statistics. These methods yield, among others, $K(25)\ge197580$, $K(27)\ge201567$, $K(38)\ge591900$, $K(43)\ge2553792$, $K(45)\ge7380090$, and $K(55)\ge53301140$. The autonomous system carried out the construction searches, mathematical analysis and computational verification, while each final result was reduced to explicit mathematical arguments and independently checkable finite certificates. Our results illustrate how autonomous research systems can move beyond optimization within fixed formulations to discover new mathematical representations and constructions at scale.
Read the full abstract

All authors Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Fujia Chen, Kaihao Zhu, Wenhao Li, Zichen Li, Yaqi Li, Shenzhan Hong, Yuang Pan, Junjie Yang, Taowen Deng, Jincheng Mi, Hongsheng Chen, Yihao Yang

Information Theory

A proof of the generalized packing-covering conjecture

The generalized packing–covering conjecture of Elimelech, Firer and Schwartz asserts that, for every linear code $\mathcal{C}$ and every admissible order $t$, the $t$-th generalized Hamming weight $d_t(\mathcal{C})$ and the $t$-th generalized covering radius $R_t(\mathcal{C})$ satisfy $d_t(\mathcal{C})\le 2R_t(\mathcal{C})+2$. We give a computer-assisted proof of the conjecture for every linear code over every finite field and every admissible order. Combining a parity-check reformulation of the conjecture, bounds on the length of putative counterexamples, and successive puncturing arguments, we settle all orders $t\ge 32$ and reduce the remaining orders to finitely many parameter tuples, which we exclude by an exact computer verification.
Read the full abstract

All authors Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri, Rocco Trombetti

Information Theory

Divergence-Minimizing Distribution Matching for Parallel Channels and Channels with Memory

Theory for distribution matchers (DMs) is extended to distributions with memory. The divergence-minimizing DM is shown to select the sequences with the highest target probability, as in the memoryless case. A scaling law for divergence is extended to distributions driven by innovation processes. The theory is applied to parallel additive white Gaussian noise channels. A modified enumerative sphere-shaping (ESS) method with a weighted energy constraint is used in implementations. An illustrative example with three channels shows that joint ESS across channels reduces the rate loss by a large factor compared to product DMs at short blocklengths. The gains are confirmed by simulations with probabilistic amplitude shaping and a 5G-NR low-density parity-check code.
Read the full abstract

Information Theory

GPU-Accelerated Robust Beamforming for OTFS Massive MIMO with CSI Uncertainty

This paper focuses on robust beamforming for orthogonal time frequency space (OTFS)-enabled massive multiple-input multiple-output (MIMO) systems under channel state information (CSI) uncertainty. In high-mobility satellite communications, uncertain CSI severely degrades beamforming accuracy and poses a major challenge to meeting users' quality of service (QoS) requirements. To address this challenge, we first formulate a chance-constrained optimization problem aiming to minimize the total transmit power while guaranteeing a predefined outage probability. Building on a 3D delay-Doppler-angle (DDA) channel representation, we propose a data-driven approach using support vector clustering (SVC) to model the uncertain CSI as an asymmetric uncertainty set. We then derive a robust counterpart that reformulates the intractable chance constraints into a deterministic semidefinite program. Finally, we design a graphics processing unit (GPU)-accelerated parallelizable alternating direction method of multipliers (ADMM) algorithm to address the computational complexity of large-scale antenna arrays. Simulation results show that the proposed SVC-based design reduces transmit power compared with conventional beamforming schemes, and that the GPU-accelerated ADMM achieves a speedup. These results confirm that the proposed framework achieves improved robustness, energy efficiency, and efficient computation in dynamic massive MIMO networks.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Information-Theoretic Analysis of Next-Token Prediction under Markovian Data

We develop an information-theoretic framework for generalization in next-token prediction under temporally dependent data. We consider independent trajectories generated by finite-memory Markov processes and distinguish algorithmic dependence, quantified by mutual information, from temporal dependence, characterized by mixing. For cross-entropy loss, we derive an expected generalization bound using the Donsker–Varadhan variational representation and a McDiarmid-type concentration inequality for Markov chains. A refinement captures the joint effect of context length and temporal mixing through the mixing properties of the history-state process. We then extend the bound through a rate–distortion formulation, replacing mutual information with the minimum information rate required to represent the learned model within a prescribed distortion in the generalization gap, yielding informative guarantees for deterministic algorithms over continuous hypothesis spaces. For margin-based prediction, we derive explicit bounds for linear and self-attention next-token predictors via noisy low-dimensional compression, revealing the roles of context length, model complexity, sample size, margin, and temporal mixing. Experiments on TinyStories and ETTh2 show that longer contexts can reduce both training and test losses, but typically reduce training loss more, enlarging the generalization gap. A complementary ETTh2 analysis identifies an effective predictive-memory scale near 24 hours, with no statistically supported improvement beyond this scale, offering a plausible explanation for test-performance saturation at larger contexts.
Read the full abstract

Information Theory

Robust Resource Management for SAGIN using DNN-Driven Channel Uncertainty Learning

This paper focuses on the joint robust beamforming and resource allocation for space-air-ground integrated networks (SAGIN) under uncertain channel state information (CSI). In SAGIN, uncertain CSI undermines the precise adjustment of beamforming and resource allocation, posing a major challenge to meeting heterogeneous users' strict quality of service (QoS) requirements. To address this challenge, we first formulate a chance-constrained optimization problem to minimize the total transmit power while satisfying QoS requirements under a predefined outage probability. By leveraging semidefinite relaxation (SDR), the objective function is transformed into a linear function of the traces of the beamforming matrices. Then, we propose a deep neural network (DNN)-driven channel uncertainty learning to dynamically learn and model the uncertain CSI as an asymmetric uncertainty set. Under the constructed CSI uncertainty set, a robust counterpart method based on pre-trained network parameters is developed. It characterizes the uncertainty set as a finite union of convex sets, thereby providing a tractable approximation for the original chance constraints. Finally, we design an adaptive iterative algorithm to jointly optimize the resource allocation and beamforming vectors. Simulation results show that our proposed DNN-driven method outperforms traditional robust and non-robust methods, achieving a superior energy efficiency and robust reliability in SAGIN.
Read the full abstract

All authors Haonan Zhang, Weihua Wu, Qi Zhang, Runzi Liu, Zewei Jing, Weijia Han

Information Theory

Covert Communications over Enormous Fluid Antenna Systems (E-FAS): Impact of Channel Hardening on Detection

Enormous fluid antenna systems (E-FAS) enable guided surface wave (SW) propagation and induce an end-to-end channel that is conditionally complex Gaussian with a random covariance scale. This paper investigates the impact of this channel structure on covert communication in the presence of a passive warden. Under an equal power effective mode representation, the random channel scale follows a Gamma distribution, leading to a Bessel-K distribution for the effective channel power. We show that the optimal likelihood ratio test at the warden reduces to an energy detector and derive the corresponding false alarm and missed detection probabilities. These results are then used to characterize the achievable covert throughput under a prescribed detection error constraint. Numerical results show that, for finite observation intervals, finite mode E-FAS channels improve covertness relative to the fully hardened Rayleigh limit with the same average channel power. They further reveal an asymmetric role of channel hardening: stronger hardening can improve the legitimate link, whereas retaining channel scale fluctuations at the warden can enhance finite observation covertness.
Read the full abstract

All authors Farshad Rostami Ghadi, Damoon Shahbaztabar, Kai-Kit Wong, Wei-Ping Zhu

Information Theory

Contraction of Rényi Divergences for Discrete Channels

We investigate Strong Data-Processing Inequality (SDPI) constants for Rényi Divergences on finite spaces. We study their dependence on the Rényi order $\alpha$, proving that they are non-decreasing and that their scaling by $(\alpha-1)$ is convex for $\alpha\geq1$. We also identify several support restrictions on the probability measures involved in determining these constants. In particular, in the distribution-independent setting, measures supported on a common set of at most two points suffice to evaluate the Rényi-SDPI constant. For $\alpha\in[0,1]$, we further prove equality with the $\chi^2$-SDPI constant, while at order infinity we obtain a closed-form expression. In order to link contraction over product spaces to contraction along individual coordinates, we provide tensorisation bounds for arbitrary product channels analogous to those known for $\varphi$-Divergences. At finite orders, the Rényi-SDPI constants are bounded above and below through comparisons with the $\chi^2$-Divergence and Hellinger Divergences, with sharpness established in multiple cases. At order infinity, we instead relate these constants to the contraction of Total Variation Distance. Finally, our findings are applied to local differential privacy (LDP) and the analysis of Markov chains. This yields sharp contraction guarantees for pure-LDP mechanisms, and connects Rényi-LDP to Rényi-SDPI constants. For Markov chains, we derive finite-time convergence bounds and exhibit a family of chains for which Rényi-SDPIs improve on classical $\chi^2$-based bounds by arbitrarily large factors.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Understanding Generalization Requires Universal Induction

Classical statistical theory is insufficient to explain the successes of general-purpose AI models, because it depends on handcrafted inductive biases that it cannot justify. No Free Lunch (NFL) theorems force any learner that beats chance on some environments to underperform on others. We might hope that past experience informs which environments to expect, but NFL applies equally to meta-learning. Thus, any method that makes meaningful predictions necessarily begins with an inductive bias external to the data. Choosing to bias toward short programs yields Solomonoff induction (SI), whose performance is competitive against all computable learners - albeit up to "constants" that become large when comparing against specialized methods that exploit background information. We therefore relativize SI to an information vantage point, biasing toward short programs with access to all preexisting information. This reframes the inductive bias: instead of seeking some absolute notion of simplicity, we favor accessibility with respect to our vantage point. An algorithm can only outpredict the relativized SI to the extent that its code contains additional information about the data, and no algorithm can generate such information. While SI is incomputable and hence not a practical algorithm, it provides a formal optimum for inference in the limit of infinite compute, and there is evidence to suggest that frontier AI systems roughly approximate it. Thus, the only known answer to meta-NFL is rooted in algorithmic information theory, which we should expect to play a fundamental role in explaining the generalization behavior of modern (and future) AI systems.
Read the full abstract

Information Theory · Cross-listed from cs.AI

SemRD-V2X: Closure-Guided Communication with Bounded Inference for Cooperative Perception

Vehicle-to-Everything (V2X) cooperative perception improves 3-D detection by sharing intermediate features, but dense remote features may repeat context that the ego agent can infer locally. Most communication-efficient designs optimize masks or codes empirically, leaving a more basic question open: which remote evidence is indispensable given the receiver's own observation? We introduce a closure-fidelity perspective on ego conditioned remote perception. Under a finite deductive abstraction and explicit conditions, its rate–distortion function decomposes over an irredundant core, and the exact zero-distortion rate becomes $P_A H(\pi_A)$. This analysis suggests a concrete design principle: transmit compact evidence and recover derivable context with bounded receiver-side inference. Guided by this principle, SemRD-V2X is an operational neural proxy that combines exact-budget BEV support selection, pointwise channel compression, and masked shared-weight reconstruction before standard fusion. Experiments on simulated V2XSet and real-world DAIR-V2X validate the resulting design. In a controlled five-run V2XSet comparison against a locally reproduced V2X-ViT-v1 baseline on one Tesla V100, SemRD-V2X reduces the analytical feature payload by $26.6\times$ while improving AP@0.5/AP@0.7 by 4.13/8.57 points, with 3.81% additional mean compute latency. These results position closure fidelity as both an analytical lens and an actionable design principle for communication-efficient cooperative perception.
Read the full abstract

All authors Hu Xu, Chun Li, Siyuan Qiu, Zeyan Li, Jianfeng Xu

Information Theory · Cross-listed from quant-ph

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.
Read the full abstract

Information Theory

RIS-Assisted Multiuser NOMA Networks With Imperfect CSI Under Transceiver Hardware Impairments

The incorporation of non-orthogonal multiple access (NOMA) and reconfigurable intelligent surface (RIS) provides a new solution to improve spectral efficiency. Unfortunately, the channel estimation error of RIS is noteworthy due to the absent active radio frequency link. Meanwhile, the transceivers at base stations (BS) and users also exist hardware impairments (HWI). The imperfect channel state information (CSI) and HWI will degrade the communication performance such as outage probability or data rate. To alleviate such performance deterioration, we propose a robust design scheme to minimize the BS transmit power when the target rate of users is satisfied in RIS-assisted single-beam and multi-beam NOMA networks with transceiver HWI and imperfect CSI. Further, the perfect successive interference cancellation (SIC) condition in single-beam and multi-beam NOMA networks is investigated, and the optimization problem is proposed based on perfect SIC conditions. To tackle the non-convex problem, we provide an effective algorithm combining Bernstein-type inequality and semi-definite relaxation. Numerical results demonstrate that the proposed scheme outperforms non-robust RIS-assisted NOMA scheme that ignores HWI and imperfect CSI. Moreover, the multi-beam NOMA network obtains higher beam gain compared to the single-beam NOMA network, and thus there is a superior performance in multi-beam NOMA networks.
Read the full abstract

All authors Qian Zhang, Maoyuan Wang, Xuejun Cheng, Yufei Zhao, Guanghui Luo, Shiyao Guo

Information Theory

Parallel Successive Cancellation Perturbation-Enhanced Decoding of Polar Codes via Offline Variance Design

Successive cancellation perturbation-enhanced (SCP) decoding improves the performance of finite-length polar codes by performing multiple SC decoding attempts with receiver-side perturbations. However, many existing perturbation schemes generate or update subsequent perturbations according to the outcomes of previous decoding attempts, resulting in additional decoding latency. In this paper, we propose an offline variance design (OVD) method for parallel SCP (PSCP) decoding of short- and medium-length polar codes. First, we formulate the exact recovery objective conditioned on ordinary SC failure and classify failed frames by the position of the first genie-aided intrinsic error and the number of subsequent intrinsic errors. We also derive a consistent Gaussian representation of the perturbed channel that preserves min-sum SC hard decisions. Second, we construct a class-based approximation of the recovery objective using Gaussian approximation and backward recursions, accounting for both error correction and new errors introduced by perturbations. We prove that both the exact and analytical objectives are nondecreasing and exhibit diminishing marginal gains as independent branches are added. Third, we develop a greedy algorithm to select variances from a finite candidate set for a given code, signal-to-noise ratio (SNR), and number of perturbation branches. All variances are determined offline, allowing the original SC branch and all perturbation branches to start simultaneously. Simulations for rate-$1/2$ polar codes of lengths $64$, $128$, $256$, and $512$ show that OVD-PSCP achieves lower block error rates (BLERs) than conventional SCP with the same number of perturbation branches. The gains are larger for shorter codes and increase as the number of perturbation branches grows.
Read the full abstract

Sunday 27 September

Information Theory

Statistical Dark Matter: Synergy is everywhere but is hard to capture

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

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

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

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

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

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

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

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

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

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

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

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

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

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