Peer Revenue Fully funded

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)

Wednesday 12 August

Information Theory

Channel Estimation for OTFS Systems With Overspread Doppler Shifts

In this paper, we consider an orthogonal time frequency space (OTFS) system in time-varying channels with overspread Doppler shifts, typically found in non-terrestrial multi-satellite links. The overspread Doppler shifts with magnitude greater than half of the subcarrier spacing, result in aliased Doppler shifts in the delay-Doppler (DD) domain due to the OTFS modulo operation. This makes channel estimation very challenging and the traditional channel estimation methods become ineffective. To address this challenge, we propose a DD training frame and a two-stage channel estimation method. The training frame comprises a cosine pilot signal and a pilot symbol. In the first stage of the channel estimation, the pilot symbol in the DD domain is utilized to estimate the delays, aliased Doppler shifts, and channel gains of the propagation paths. In the second stage, the received time domain signal is converted into the frequency domain to detect the peaks of all the Doppler shifts using the cosine pilot signal. Then, we present a threshold-based method to pair the estimated actual Doppler shifts with their corresponding delays and channel gains. The complexity of the proposed channel estimation is also discussed. Finally, the performance of the proposed channel estimation is validated in terms of the normalized mean square error (NMSE) and bit error rate (BER) in various scenarios.
Read the full abstract

Information Theory · Cross-listed from cs.AI

MindMemOS: A Portable and Self-Evolving Memory Operating Layer for AI Agents

Memory is a core component of AI agents, enabling them to accumulate experience, maintain personalization, and adapt over long-term interactions. However, existing memory systems often remain fixed after development, limiting their ability to adapt their memory models, organization strategies, and procedural knowledge through continued use. We present MindMemOS, a portable and self-evolving memory operating layer that organizes open-world information using a unified entity property timestructure. MindMemOS supports scenario-adaptive memory modeling, higher-order pattern discovery, autonomous memory refinement, and continuous skill evolution. Its MindMemEvolve algorithm employs validation-driven evolutionary search to optimize memory schemas for target scenarios, whiledreaming consolidates accumulated memories by merging redundant records and resolving conflicts. In addition, implicit corrective feedback serves as a human-in-the-loop signal for identifying and revising potentially inaccurate or misaligned memories. Its MindSkillEvolve algorithm further transforms agent execution trajectories into reusable and progressively refined skills. MindMemOS achieves 94.03% accuracy on LOCOMO and 70.63% on PersonaMem. MindSkillEvolve improves SpreadsheetBench success by 9.2 percentage points over the initial-skill baseline.
Read the full abstract

All authors Kaichao Liang, Yuqi Cui, Hao Kong, Xinyuan Huang, Guohaotian Hou, Qingcan Kang, Liang Chen, Yiyang Yin, Ke Ye, Jiaquan Guo, Da Chen, Lingan Zeng, Yixing Peng, Rong Yao, Shixiong Kai, Mingxuan Yuan

Information Theory

New optimal linear codes over $\ZZ_4$

In this work, we present novel approaches for constructing linear codes over $\ZZ_4$ from the known ones. We succeeded in obtaining new linear codes, many of which are optimal. In particular, we found all optimal codes for $k_1=2,~k_2=0$ and many optimal codes for $k_1=3,~k_2=0.$

Information Theory

Satellite Infrastructure Sharing: Orbit-Structured Stochastic Geometry Modeling and Connectivity Analysis in Heterogeneous Satellite Networks

This paper develops an analytical framework to evaluate the feasibility and performance of satellite infrastructure sharing among multiple low Earth orbit (LEO) satellite operators. Motivated by the growing demand for universal connectivity under limited satellite resources, the proposed model captures uncoordinated deployments where independently operated constellations coexist without predefined orbital agreements. To describe such heterogeneous configurations, the spherical Cox point process is employed to jointly generate orbital structures and satellites. Then, each satellite is further assigned a random communication range, reflecting variations in coverage capability across operators. The overall coverage region is modeled through a spherical Cox-Boolean model that captures the spatial overlap of individual satellite spherical footprints on Earth. Using the proposed framework, the feasibility and benefits of satellite infrastructure sharing are mathematically analyzed, and closed-form expressions are derived for key performance metrics such as the connection probability, connection number, and downlink signal characteristics including the nearest serving distance, total received signal power, and the signal-to-interference ratio (SIR) distribution in the interference-limited regime. The analytical results, validated through system-level simulations, provide a tractable characterization of how orbital geometry governs coverage, connectivity, and interference, and reveal the inherent trade-offs induced by coverage overlap in heterogeneous satellite constellations.
Read the full abstract

Information Theory

Lossy Compression, Realism, and Coordination

Classical rate-distortion theory characterizes the fundamental limits of lossy compression under fidelity constraints, but minimizing distortion often yields perceptually unsatisfying reconstructions - blurry images, over-smoothed textures, and unnatural artifacts. This has motivated a growing body of work on compression with realism constraints, which require reconstructions to be statistically indistinguishable from natural signals, giving rise to the three-way rate-distortion-perception (RDP) trade-off. This paper provides an accessible overview of this emerging area and reveals deep connections to another fundamental problem: distributed coordination under rate-limited communication. Under strong distribution matching formulations, both problems lead to nearly identical information-theoretic characterizations, both require common randomness (CR) for optimal performance, and both rely on similar analytical tools such as the soft covering lemma. Beyond a unifying perspective, we survey recent developments in formalizing realism, including batched critics and algorithmic realism, and propose to transfer such paradigms to coordination - illustrating how the connection continues to generate new problems.
Read the full abstract

Information Theory

The Optimal Discounting Parameter of the Power Prior under Predictive Log-Loss

The power prior of Ibrahim and Chen incorporates historical data into a Bayesian analysis by raising the historical likelihood to a power $a_0 \in [0, 1]$. The choice of the exponent has remained an open question. This paper gives a closed-form answer under the predictive log-loss. For a model with $d$ parameters, a historical sample of size $N_0$, and average Kullback–Leibler divergence $\bar{D}_0$ between the historical and current data-generating distributions, the optimal exponent is $a_0^{*} = d/(2 N_0 \bar{D}_0 + d)$. Equivalently, the optimally borrowed effective sample size obeys the harmonic law $1/E^{*} = 1/N_0 + 2\bar{D}_0/d$: compatible data are pooled in full, and any difference caps the borrowed information at $d/(2\bar{D}_0)$ observations. The result is exact for multinomial data and extends to smooth parametric families. The law benchmarks adaptive borrowing, explains the reported degeneracy of the normalized power prior, and shows that neither subsetting the data nor decaying the exponent improves on the correctly discounted constant.
Read the full abstract

Information Theory

Secure Coverage Enhancement in Aerial Reconfigurable Intelligent Surface-Assisted High-Speed Train Communication Systems

High-speed trains (HSTs) have become a prominent means of transportation, requiring high data rates and reliable communication services for HST passengers. However, the wireless channels in HST communication systems are susceptible to various security threats, including eavesdropping. Addressing these security concerns is therefore of critical importance. One promising technology for enhancing security is the integration of a reconfigurable intelligent surface (RIS) on an unmanned aerial vehicle, referred to as an aerial reconfigurable intelligent surface (ARIS). This technology offers significant potential for improving wireless network performance, though it also introduces unique challenges in terms of physical layer security (PLS). This paper investigates the PLS of ARIS-aided HST communication systems. A problem of maximizing the weighted sum secrecy rate is formulated by jointly optimizing the active beamforming at the base station (BS) and the phase shift at the ARIS, subject to constrains on the BS transmit power and the unit modulus of the ARIS reflecting coefficient. To address this problem, a joint optimization algorithm is proposed using the block coordinate descent method. Specifically, the problem is decomposed into two subproblems: active beamforming design and ARIS phase shift optimization. The active beamforming is optimally designed via the successive convex approximation technique, while the ARIS phase shift is efficiently updated using the alternating direction method of multipliers technique. Simulation results demonstrate the rapid convergence of the proposed algorithm, which achieves a higher secrecy rate compared to existing methods in the literature.
Read the full abstract

All authors Changzhu Liu, Ruisi He, Bo Ai, Yong Niu, Zhu Han, Gongpu Wang, Haoxiang Zhang, Jiahui Han, Zhangdui Zhong

Information Theory

AFDM-ISAC With Fractional Delay-Doppler Coupling

Affine frequency division multiplexing (AFDM) is a promising chirp-based multicarrier waveform for high-mobility integrated sensing and communication (ISAC). Accurate angle, delay, and Doppler estimation is essential for AFDM sensing. Since target delays and Doppler shifts are generally continuous-valued, representing them on a discrete delay–Doppler grid causes energy leakage and peak displacement in the discrete affine Fourier transform (DAFT) domain. The AFDM chirp also induces delay–Doppler coupling in the DAFT-domain response. The resulting DAFT-domain matching-score surface exhibits a local ridge that is not aligned with the normalized-delay and normalized-Doppler axes. To address these issues, this paper investigates joint estimation of angle and continuous-valued delay–Doppler parameters for a colocated AFDM-ISAC sensing architecture. A transform-domain sparse sensing model is formulated from the fractional DAFT-domain response. Based on this model, a coupled-coordinate Newtonized orthogonal matching pursuit (CC-NOMP) estimator is developed. CC-NOMP uses the AFDM-induced coupling coordinate to parameterize the dominant local ridge. It combines coupled-coordinate Newton refinement with safeguarded updates, coupling-aligned delay refinement, and cyclic multi-target refinement to estimate angle, continuous normalized delay, and normalized Doppler. A deterministic Cramér–Rao bound and a dominant-order complexity analysis are also derived. Simulation results with continuous-valued off-grid target parameters show that CC-NOMP achieves lower delay and Doppler error floors than the considered baselines while maintaining comparable angle-estimation accuracy.
Read the full abstract

All authors Shaohua Li, Cunhua Pan, Hong Ren, Ruizhe Wang, Jiangzhou Wang

Information Theory · Cross-listed from quant-ph

Uniformly Stable Minimal Weyl–Heisenberg Measurements Approaching the SIC Benchmark

Informational completeness (IC) guarantees that an inverse exists, not that it is statistically well conditioned. For minimal rank-one Weyl–Heisenberg (WH) measurements, covariance makes the nonidentity projector-Gram spectrum proportional to the fiducial's ambiguity intensities, with eigenvalues \(d|\chi_\phi(u)|^2\), turning stability into an explicit worst-direction design problem; write \(\lambda\) for its smallest nonidentity eigenvalue. Haar fiducials are IC almost surely while \(\mathbb E[\lambda^{-1}]=\infty\), and an explicit geometric family used to establish balanced informationally complete measurements in every dimension has a normalized spectral floor bounded above by an exponentially decaying envelope. We then construct a hierarchy of minimal measurements. A cyclic family with exactly \(d^2\) outcomes in every integer dimension has floors \(\Theta(d^{-3})\) for odd \(d\) and \(\Theta(d^{-5})\) for even \(d\); a finite-field family for \(q=2^m\) obeys the uniform bound \(\lambda\ge4/9\). Our main result treats every prime-power dimension of characteristic \(p\ge5\). A balanced one-coordinate perturbation repairs the zero ambiguity axis of a cubic Alltop state, gives an attained floor uniformly bounded below by a positive constant, and confines the entire nonidentity spectrum to \([L_q,U_q]\) with \(U_q/L_q\to1\). Its SIC-normalized minimum tends to one, and \(\lambda(\phi_q)/\Lambda_q^\star\to1\) for the global finite-field WH max–min optimum \(\Lambda_q^\star\), without assuming SIC existence. The complete spectrum determines the exact finite-sample Hilbert–Schmidt error of canonical linear inversion at \(I/d\), while its lower edge controls local Fisher efficiency and canonical-shadow bounds.
Read the full abstract

Information Theory · Cross-listed from eess.SP

A Universal Random Precoding Framework for MIMO Systems

Current wireless systems combat inter-symbol interference (ISI) by diagonalizing or sparsifying the channel matrix, yet they remain vulnerable to selective fading. To address this, we propose a universal random precoding (RP) transmission framework based on the universality class. RP leverages random transforms to statistically exploit all subchannels and construct an equivalent channel belonging to the universality class, thereby enhancing diversity gain while maintaining backward compatibility with existing waveforms. Low-complexity implementations include the randomly permuted fast transform (FT-RP) and the interleaved block-sparse fast transform (IBSFT-RP). A cross-domain OAMP/MAMP (CD-OAMP/MAMP) detector is designed for RP systems, which is replica maximum a posteriori (MAP)-optimal according to state evolution (SE). Simulation results on MIMO systems demonstrate that RP with CD-OAMP/MAMP achieves near-RM performance with much lower complexity, with additional benefits of flexible compression ratios for spectral efficiency.
Read the full abstract

All authors Jiazhen Dong, Lei Liu, Xiaojun Yuan, Baoming Bai

Information Theory

Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy

We introduce partial path interception on derivation DAGs (directed acyclic graphs), a combinatorial optimization problem arising from proof-valid caching: stored objects must be logical consequences of a premise base whose premises are erased independently, a query is recovered only while derivable from surviving premises and stored objects, and the queried object itself may not be stored, so reliability must come from premises or intermediate consequences. An exact residual-leaf law pins the recovery probability to a closed form in the exposed-leaf count and reduces design to weighted partial path interception (PPI) on the witness DAG. We classify PPI across its canonical regimes: it is NP-complete already on depth-two DAGs with leaf out-degree two and fixed-parameter intractable in the budget, ruling out efficient approximation schemes; it contains smallest T-edge subgraph as a special case, hence admits no approximation within the square root of the optimum under the Strongish Planted Clique Hypothesis, matched there by trivial leaf-only caching; whereas unique-path instances admit an exact dynamic program, bounded-treewidth instances are fixed-parameter tractable, and individual coverage admits a tight logarithmic greedy guarantee. Semantic-module caches are exactly optimal for shared workloads under exact module routing. An appendix prices transparency against a coded erasure benchmark.
Read the full abstract

Information Theory

Complete characterization of the differential spectrum of a Niho type power function

Power functions with Niho exponents have attracted considerable attention due to their important applications in sequence design, coding theory, and cryptography. This paper investigates the differential properties of Niho type power functions of the form $F(x)=x^{s(2^m-1)+1}$ over $\mathbb{F}_{2^{2m}}$ with $2\leq s\leq 2^m$. We first establish a general characterization of the differential spectrum of $F(x)$ having at most three nonzero values via its Walsh spectrum. Focusing subsequently on the case $s=(2^k+1)^{-1} \pmod{2^m+1}$ where $\gcd(k,m)=e$, we employ a refined analysis of the number of solutions to certain equations over finite fields. Specifically, it is proved that $F(x)$ is locally differentially $2^e$-uniform when $\gcd(2^k-1,2^m+1)=2^e+1$ and locally differentially $(2^{2e}-2^e)$-uniform when $\gcd(2^k-1,2^m+1)=1$, and their differential spectra are completely determined. These results completely characterize the differential properties of this family and yield new infinite families of locally differentially $4$-uniform power functions.
Read the full abstract

All authors Nian Li, Xi Xie, Rui Xu, Yi Yu, Xiangyong Zeng

Information Theory · Cross-listed from eess.SP

Characterizing Nonlinearities in IM-DD Links via the Best Linear Approximation: Distortion Analysis and Modulation Optimization

We use the best linear approximation (BLA) to characterize nonlinearities in IM-DD links. The orthogonal nonlinear distortion is shown to be non-Gaussian. The BLA is used to approximate the optimum modulation depth for different equalizer structures.
Read the full abstract

All authors Sebastian Fraga Fernández, Leonardo Minelli, Fernando de Bernardinis, Felipe Villenas, Yunus Can Gültekin, Alex Alvarado

Information Theory

Sparse Rotatable Arrays (SRA): Unifying Array Aperture and Antenna Directivity for Wireless Communications

Sparse rotatable array (SRA) is a novel reconfigurable antenna architecture that jointly exploits sparse aperture configuration and antenna directivity to enhance spatial resolution for future wireless communications. Specifically, SRA activates a subset of rotatable antennas over a large candidate aperture and adjusts their boresight directions, thereby creating a directionally selective sparse aperture with reduced hardware requirements and enhanced spatial flexibility. In this paper, we investigate an SRA-aided multi-group communication system, where users are organized into spatial groups with different service requirements. We develop a group-aware SRA design framework by jointly optimizing the sparse-aperture allocation, RA orientations, and transmit beamforming to maximize the weighted max-min signal-to-interference-plus-noise ratio (SINR). Then, we characterize the operating principles of SRA and reveal that sparse aperture improves spatial resolution by enlarging the effective array aperture, while antenna directivity suppresses inter-group coupling through directional control, thereby enabling simplified group-wise beamforming structures. Guided by these insights, we develop a structured low-complexity alternating optimization algorithm that embeds a closed-form projected group-center RA orientation rule into the sparse-aperture allocation and beamforming design. The proposed algorithm combines analysis-guided initialization, sampled multi-start antenna-allocation search, and bisection-based second-order cone programming for beamforming. Numerical results show that the proposed SRA design closely approaches fully-shared SRA benchmarks and significantly outperforms compact subarray and omni sparse-array schemes.
Read the full abstract

All authors Ailing Zheng, Qingqing Wu, Xiyuan Liu, Wen Chen

Information Theory

An AoI-oriented Time-Frequency Distributed Access Mechanism in Wireless Sensor Networks with Spectrum Division

The increasing adoption of spectrum-division techniques enables concurrent uplink transmissions over multiple orthogonal resources, yet low-overhead access design with effective information freshness remains insufficiently studied for large-scale randomly activated sensor networks. In this paper, we apply the age of information (AoI) to measure information freshness and propose an AoI-efficient deterministic time-frequency distributed access (D-TFDA) mechanism. D-TFDA combines centralized configuration and distributed operation through a periodic token-based time-frequency structure, which provides sensors with collision-free and predictable transmission opportunities without considerable run-time overhead. We develop an analytical framework to characterize the long-term average AoI (AAoI) by exploiting the periodicity of the token assignment pattern and modeling the steady local state of each sensor with a one-dimensional discrete-time Markov chain (DTMC). We further reveal structural properties of the token assignment pattern and identify AoI-equivalent token clusters, which substantially reduce the search space of the AAoI-optimal token allocation problem. Based on this structure, we formulate the reduced problem as a linear programming (LP) problem and develop an AAoI-optimal search algorithm, together with an auction-inspired heuristic algorithm of lower complexity. Simulation results validate the proposed AAoI analysis, demonstrate the effectiveness of the token allocation algorithms, and show that D-TFDA achieves substantially lower AAoI than optimized random access baselines by avoiding collisions and exploiting heterogeneous sensor–resource transmission reliability.
Read the full abstract

All authors Jingwei Liu, Fang Liu, Wing Shing Wong, Yuan-Hsun Lo, Chung Shue Chen

Information Theory

Semantic Error Control Coding with Foundation Models for Future Communications

Classical channel decoding typically treats all information sequences as equally likely and relies primarily on the channel observations and code structure, without exploiting statistical or semantic structure in the source data. Although source compression is designed to remove redundancy, practical source coding can leave substantial residual structure that conventional channel decoders do not exploit. Modern multimodal data sources, including text, speech, and images, exhibit rich statistical and semantic dependencies that foundation models can learn and exploit to improve channel decoding. This article introduces semantic error control coding (SECC), which seamlessly integrates the semantic structure of the source into encoding and decoding through a foundation model. The semantic source prior, represented by the model's a priori probability of the source content, directs code redundancy toward semantically important content at the encoder, and improves reliability estimation, candidate search, and error detection/correction at the decoder. The channel code keeps its algebraic structure, and its constraints ensure that the semantic suggestions from the foundation model comply with this structure. We describe the SECC framework, classify its design methods into three approaches, and demonstrate representative schemes on text sources. The demonstrated schemes show several decibels of coding gain over conventional decoding on AWGN channels, and reach error rates below the normal approximation bound. Finally, we identify several open challenges.
Read the full abstract

All authors Chentao Yue, Gaoyang Pang, Branka Vucetic, Yonghui Li

Tuesday 11 August

Information Theory

When to Stop? Dynamic Early Termination of Sequential Ensembles

Ordered-statistics decoding (OSD) post-processing substantially improves the performance of belief propagation (BP) ensembles, but it also removes their natural syndrome-based stopping criterion. The high computational complexity of ensemble decoding and OSD can be reduced by sequential activation of ensemble members paired with an early termination. Instead of a syndrome-based termination we therefore apply dynamic ensemble termination (DET) to sequential ensembles: members are evaluated one at a time and decoding stops when the estimated risk that an unseen member would correct the current decision falls below an offline-fitted threshold. With hardware-oriented design in mind, we instantiate the framework with layered normalized min-sum component decoders, a row-boosted ensemble, conditional low-order OSD on the dual code, and a conventional low-cost decoder gate. A decision tree estimates the residual risk from statistics of the current candidate list. Member-dependent thresholds then target a prescribed frame error rate (FER) loss. We validate this framework on mutliple IEEE 802.11 low-density parity-check (LDPC) codes with blocklengths \(648,1296\), and \(1944\) at rates \(1/2\) and \(5/6\). At each code's design point, where the full \(64\)-member list reaches an FER of \(10^{-3}\), the DET decoder processes \(1.04\) to \(1.15\) members on average. On the \((648,540)\) code, it reduces BP work by \(39\times\) and OSD activations by \(18\times\) against the full list while retaining an signal-to-noise ratio (SNR) gain of about \(0.4\,\mathrm{dB}\).
Read the full abstract

Information Theory · Cross-listed from eess.SP

Hardware-in-the-Loop Phase-Aware CNN for Real-Time 5G Channel Estimation

This demo presents real-time AI-based uplink channel-estimation inference using data collected from a hardware-in-the-loop 5G platform. The data-collection setup integrates commercial RF signal generation, programmable channel emulation, an O-RAN Radio Unit, DU emulation, and a lightweight phase-aware convolutional neural network (CNN) that estimates the channel response directly from received DMRS signals. Unlike simulation-only evaluations, the hardware-derived dataset exposes the estimator to practical RF and system-level impairments, including calibration mismatches, synchronization imperfections, quantization effects, phase noise, and implementation-specific nonlinearities. During the demo, attendees will observe real-time CNN inference and channel reconstruction using captured hardware-generated DMRS observations and compare the proposed CNN against Least Squares (LS) and frequency-domain LMMSE baselines. The objective is to showcase a practical AI-native physical-layer inference pipeline that combines hardware-derived 5G data with real-time neural channel estimation for future 5G-Advanced and 6G systems.
Read the full abstract

All authors Javad Zolfaghari-Bengar, Rakibul Rony, Elisa Gomez-de-Lope, Alejandro Villena-Rodriguez, Abhinav Mahadevan, Nicolas Kourtellis

Information Theory · Cross-listed from quant-ph

Quantum Codes with Arbitrary Z-Rotation logical Gates and Applications to Fault-Tolerant Code Switching

A technique for realizing a universal set of fault-tolerant quantum operations is the code switching method, which leverages two quantum codes with complementary sets of transversal gates. To date, the application of this technique has been largely limited to families of color codes supporting a logical $T$ gate. No analogous code switching protocols exist for many other prominent families, such as rotated surface codes, or for finer $Z$-rotation gates. In this work, we first utilize the doubling technique as a unified framework to construct a class of quantum color codes encoding a single logical qubit with an arbitrarily large minimum distance, enabling the transversal realization of arbitrary small logical $Z$-rotation gates. We investigate the structural properties of this code family, demonstrating that they improve upon the parameters of state-of-the-art triorthogonal codes, achieve lower qubit overhead compared to certain known color codes, and admit single-shot decoding of $Z$-syndromes via meta-checks. Furthermore, we show that this framework extends beyond color codes; specifically, it enables the generation of $r$-orthogonal quantum codes, $r \ge 2$, that inherit the local geometry of rotated surface codes. We then provide an overhead optimization protocol alongside several candidate codes tailored for realizing logical $Z$-rotation gates within rotated surface codes. Finally, we extend the fault-tolerant code switching protocol based on transversal CNOT gates to incorporate fault-tolerant realization of $Z$-rotation gates at any level of the Clifford hierarchy for geometries compatible with rotated surface codes. We present the first demonstration of fault-tolerant magic state preparation by means of code switching within a distance-three rotated surface code using a total footprint of only 45 physical qubits, and evaluate its performance through a simulation.
Read the full abstract

All authors Reza Dastbasteh, Ruben M. Otxoa, Pedro M. Crespo, Josu Etxezarreta Martinez

Information Theory · Cross-listed from quant-ph

Optimal von Neumann Entropy Estimation

We show that the von Neumann entropy of an unknown $d$-dimensional quantum state $\rho$ can be estimated to within additive error $\varepsilon$ using \[ \Theta\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) \] samples of $\rho$, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.
Read the full abstract

Information Theory

Twisted Conjugacy and the Classification of Induced Centrosymmetric Alternant Codes

This paper presents a classification of induced centrosymmetric alternant codes through the study of the automorphism structures inherited from Generalized Reed–Solomon (GRS) codes. We introduce the twisted conjugation action naturally associated with projective semilinear transformations and establish its correspondence with ordinary conjugacy in the projective semilinear group. This correspondence enables the application of Shintani's theorem to classify the $\gamma_{p^j}$-similarity classes of involutions. As a consequence, we obtain necessary and sufficient conditions for an alternant code to admit a centrosymmetric structure induced by a projective semilinear automorphism. The resulting classification unifies the different families of induced centrosymmetric alternant codes within a common automorphism-based framework.
Read the full abstract

Information Theory · Cross-listed from math.PR

A Bayesian Proof of the Bernoulli Theorem

We give a new proof of the Bernoulli theorem, conjectured by Talagrand and proved in the seminal work of Bednorz and Latała. Our approach is based on information-theoretic ideas: lower bounds on the supremum of a Bernoulli process are translated to the fundamental limits of Bayesian estimation in a Cauchy additive channel. This leads to a new information-theoretic functional that characterizes Bernoulli-process suprema and plays a role analogous to Fernique's majorizing-measure functional for Gaussian processes. The same viewpoint yields a distributional strengthening: for any prescribed law of the index, we characterize the largest expected value attainable over all couplings of that index with the Bernoulli process. This extends to Bernoulli processes a phenomenon previously understood for Gaussian processes through the work of Fernique and Talagrand.
Read the full abstract

Information Theory

Information Bottleneck under Perfect Privacy

In this work, we study the information bottleneck under perfect privacy, with particular emphasis on the active-rate regime, where the representation-rate constraint is binding and directly limits the achievable utility. The goal is to construct a representation that preserves utility-relevant information while remaining statistically independent of a sensitive variable. This exact independence requirement introduces an additional constraint beyond the classical rate-relevance tradeoff and must be explicitly incorporated into the optimization. To this end, we develop an alternating direction method of multipliers (ADMM)-based method tailored to the resulting problem structure. Under suitable regularity conditions, we establish global convergence of the generated sequence, characterize its convergence rate through the Kurdyka-Lojasiewicz exponent, and extend the analysis to inexact block updates.
Read the full abstract

Information Theory · Cross-listed from quant-ph

The entanglement-assisted transmission capacity is a strong converse bound for identification

Classical identification via a noisy channel is a communication task in which the receiver is not required to reconstruct the full transmitted message, but only to decide whether it coincides with a message of interest. This relaxation allows the number of identifiable messages to grow doubly exponentially with the blocklength. For quantum channels, the resulting (doubly exponential) identification capacity $C_{\mathrm{ID}}$ can strictly exceed the ordinary (exponential) transmission capacity $C$. In this paper, we prove that the entanglement-assisted transmission capacity $C_E$ is a strong converse bound for this task: $C_{\mathrm{ID}}\leq C_E$. For sufficiently low-noise channels, this bound can also be achieved via the Hayden-Winter (quantum) identification + fingerprinting codes. This yields an exact characterization $C_{\mathrm{ID}}=C_E$ of identification capacity for such channels. However, for general channels, we prove that this upper bound can be strict. We exhibit an explicit family of transpose-depolarizing channels for which $C_{\mathrm{ID}}<C_E$. As a consequence, we also obtain the first example of strict superadditivity of the identification capacity $C_{\mathrm{ID}}$.
Read the full abstract

Information Theory

Search-to-Decision Reductions for the Linear and General Code Equivalence Problems

In this paper, we present efficient search-to-decision reductions for the Linear Code Equivalence (LCE) and Generalised Code Equivalence (GCE) problems. Our methodology is inspired by the recent search-to-decision reduction for Permutation Code Equivalence. We demonstrate how to recover the permutation component of the equivalence using a decision oracle, and subsequently show one way of recovering the diagonal and field automorphism components in deterministic polynomial time by leveraging the elegant Engel-Schneider algorithm for diagonal equivalence.
Read the full abstract

Information Theory

Bounds for Pure Disjoint $(r,\delta)$-Quantum Locally Recoverable Codes

We study pure disjoint $(r,\delta)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill–Laflamme conditions for recovery from up to $\delta-1$ erasures within a recovery block, and introduce blockwise Shor–Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,\delta)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,\delta)$-qLRCs.
Read the full abstract

Information Theory

CSS Quantum LRCs with Intersecting Recovery Sets: Constructions and Bounds

In this work, we study $(r,t,x)$ quantum locally recoverable codes (qLRCs) with locality $r$, $t$ recovery sets per qudit, and intersection parameter $x$. We first show that, assuming the underlying classical codes have dual minimum distance at least two, a CSS code is an $(r,t,x)$-qLRC if and only if the underlying classical codes are $(r,t,x)$ classical LRCs (cLRCs) with common recovery sets. We then use subset-inclusion matrices to construct families of binary dual-containing $(r,t,x)$-cLRCs, which yield binary $(r,t,x)$-qLRCs via the CSS construction. For CSS $(r,t,x)$-qLRCs, we derive upper bounds on the dimension and rate, minimum-distance bounds in the pure case, and a Singleton-like dimension bound in the exact case. Finally, we show that these families attain high rates and nontrivial minimum distances.
Read the full abstract

All authors Evagoras Stylianou, Vinayak Ramkumar, Holger Boche, Rawad Bitar

Information Theory

Capacity regimes for Boolean function computation via channels

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$.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform

The Uhlmann fidelity ${\rm F}(\rho_0,\rho_1) = {\rm tr}|\sqrt{\rho_0}\sqrt{\rho_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $\rho_0$ and $\rho_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(\rho,|\psi\rangle\!\langle\psi|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(\rho, |\psi\rangle\!\langle\psi|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|\psi_0\rangle\!\langle\psi_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|\psi_1\rangle$ (or $|\psi_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.
Read the full abstract

Information Theory

Threshold-Based Spiking Neural Networks for Event-Driven Status Update Systems

Event-driven sensing supports energy-efficient Internet-of-Things (IoT) devices by activating communication only when relevant events occur. In such systems, transmission decisions are governed by the monitored process rather than predefined schedules. Consequently, jointly optimising information freshness and energy consumption is challenging because transmission decisions are restricted to randomly occurring events. To address this challenge, we investigate an event-driven status update system in which wake-up events follow the dynamics of the monitored process. The problem of determining whether to transmit the sensing data or not is cast as a Markov Decision Process (MDP) that jointly minimises the Age of Information (AoI) and transmission energy. We prove the existence of an optimal threshold policy, thereby obtaining an interpretable characterisation of the optimal transmission strategy. Motivated by this result, we propose a lightweight Reinforcement Learning (RL) approach based on Spiking Neural Networks (SNNs) whose architecture explicitly represents threshold policies. The resulting policy representation has constant complexity with respect to the maximum AoI and enables a more energy-efficient implementation than a comparable Artificial Neural Network (ANN). Numerical results demonstrate that the proposed SNN reliably learns optimal thresholds across different operating regimes.
Read the full abstract