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)

Thursday 30 July

Information Theory

The Capacity of a Family of Sticky Channels

We determine the capacity of a family of $q$-ary sticky-insertion channels. Fix $q\geq2$ and $d\geq1$, and let $\lambda$ be the unique positive solution of $\lambda^d = (q-1) (\lambda^{d-1} + \cdots + \lambda + 1 )$. We prove that, for every repetition law supported on $1+d\mathbb{Z}_{\geq0}$ and satisfying a coefficientwise-domination criterion with domination constant $\gamma\geq\lambda^{-d}$, the Shannon capacity equals the zero-error capacity, both being $\log_2\lambda$ bits per symbol. We also exhibit explicit repetition laws satisfying these conditions, one of which is given by the weighted Fuss–Catalan numbers. To the best of our knowledge, these are the first known cases of nontrivial repeat channels whose Shannon capacity has been determined exactly.
Read the full abstract

Information Theory

Generalized Query-Oriented Image Semantic Coding Empowered by Large AI Models and Semantic-Aware Hybrid Beamforming

Semantic communication is an emerging paradigm that can preserve the meaning of data during transmission. However, human users are often interested in specific semantic content based on their intent, and users' intent is often not considered in current semantic coding design. Moreover, most of the existing semantic models are fine-tuned using specific datasets, which limits their generalization capability. Furthermore, how to prioritize semantically important features in large-scale multiple-input multiple-output orthogonal frequency-division multiplexing (MIMO-OFDM) systems remains largely unexplored. To address the aforementioned challenges, in this paper, we propose a generalized query-oriented image semantic coding (QO-ISC) framework. In the proposed framework, the transmitter extracts features which are relevant to the user's query and the receiver reconstructs an image based on those features. We use a pretrained large artificial intelligence (AI) model (LAM) to enhance general feature representations. We develop a semantic-aware hybrid beamforming (SA-HBF) algorithm to prioritize semantically important features for large-scale MIMO-OFDM system. When evaluated on unseen object categories within the dataset, simulation results show that our proposed generalized QO-ISC framework achieves better performance than the traditional codec and two state-of-the-art semantic coding schemes.
Read the full abstract

Information Theory · Cross-listed from cs.LG

Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks

Oversmoothing is a fundamental limitation of deep graph neural networks (GNNs), where repeated message passing causes node representations to become increasingly similar, eventually collapsing toward a low-dimensional subspace. This phenomenon limits the effective depth of message-passing architectures and motivates the search for mechanisms that preserve representation diversity. In this paper, we study a recurrent graph neural network in which independent Gaussian noise is injected after every propagation step and analyze the resulting architecture as a stochastic dynamical system. Under a standard global contraction assumption on the deterministic update, we prove that the hidden representations form a geometrically ergodic Markov chain admitting a unique invariant probability measure. Our main theoretical result establishes an explicit positive lower bound on the expected stationary Dirichlet energy, proportional to both the noise variance and the spectral gap of the underlying graph. Consequently, the stationary representations cannot collapse onto the constant manifold, providing a rigorous guarantee that asymptotic oversmoothing is prevented in the sense of non-vanishing Dirichlet energy. Our analysis reveals persistent stochastic perturbations as a fundamentally different mechanism for combating oversmoothing, complementing existing deterministic approaches based on residual connections, normalization, and graph rewiring. Finally, numerical experiments on both linear and nonlinear recurrent graph neural networks closely match the theoretical predictions, illustrating the emergence of a stationary distribution and the predicted dependence of the limiting Dirichlet energy on the noise intensity.
Read the full abstract

Information Theory

On The Most Discriminative Boolean Functions for Correlated Sources

Motivated by a conjecture of Amari and Kobayashi, we study the problem of identifying pairs of Boolean functions that maximize the Kullback-Leibler divergence between two distributions obtained by separately compressing two correlated sources. When the reference distribution corresponds to independent sources, this problem reduces to the problem of maximizing mutual information, for which the optimality of dictator functions has been proved by Pichler, Piantanida, and Matz. For the problem of maximizing Fisher information, which can be viewed as a local version of the problem studied in this paper, Amari and Kobayashi conjectured that parity functions are optimal. For unbiased pairs of Boolean functions, and for identical pairs in the nonnegative correlation regime, we prove that both the divergence and the Fisher information are maximized by level-$k$ functions, namely, functions whose Fourier coefficients are supported only on level $k$. Since level-$k$ functions include parity functions, this gives a partial resolution of the conjecture of Amari and Kobayashi. Furthermore, in the framework of Bayesian distributed one-bit hypothesis testing, we prove that level-$k$ functions are optimal among all pairs of functions. Finally, we also discuss the one function version of the problem studied in this paper, which can be regarded as the divergence analogue of the Courtade and Kumar conjecture.
Read the full abstract

Information Theory

Constructing linear codes from digraphs and groups

In 2012, Kaufman and Lubotzky constructed the first family of symmetric LDPC good codes. Their construction used Cayley codes, as originally defined by Kaufman and Wigderson (2016). In this paper we present two generalisations to the Cayley code construction, which we call graph codes and digraph codes. We investigate both the algebraic, and combinatorial properties of these constructions and show that they possess the same desirable attributes as Cayley codes, but with added freedom. We analyse the relationship between the expansion properties of the ingredient (di)graphs and the parameters of the constructed codes; our analysis offers an improvement to the results of Kaufman and Lubotzky. As an application, we construct an infinite family of good digraph codes, and we propose a series of open problems.
Read the full abstract

Information Theory · Cross-listed from math.CO

A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$

We give a recursive reformulation and extension of the independent set of size $134753$ in $C_7^{10}$ constructed by N. Itty, C. D. Rosin, C. Carstensen, and D. Reichman (arXiv:2607.21517v1). We prove a product lemma that combines gadgets of different dimensions while preserving the required independence conditions. Starting from the size-$367$ independent set in $C_7^5$ of S. C. Polak and A. Schrijver (Information Processing Letters 143 (2019), 37-40), the construction gives an explicitly specified independent set in $C_7^{200}$. Consequently, \[ \Theta(C_7)\geq 3.2587891539086910161967650155\ldots . \] An accompanying program verifies the finite assertions about the five-dimensional base gadget and performs the exact integer computations used in the recursion.
Read the full abstract

Information Theory

Green Cell-Free Massive MIMO for ISAC: Joint Cloud, Fronthaul and Radio Resource Allocation

In this paper, we develop a cross-layer end-to-end (E2E) resource orchestration framework for green CF-mMIMO ISAC systems with distributed multi-target detection. We propose a distributed sensing approach in which receive access points (RX-APs) compute local test statistics, which are aggregated at the cloud using weights based on sensing interference and channel quality. We derive the local maximum a posteriori ratio test (MAPRT) detectors under fully informed (FIS) and partially informed (PIS) operation, representing different levels of transmit-signal information at the RX-APs. We further characterize their processing and fronthaul requirements and derive a network power model incorporating radio transmission, AP and cloud processing, and fronthaul infrastructure. We formulate a mixed-integer non-convex problem that jointly optimizes transmit powers, AP modes, UE and sensing-area associations, RX-AP assignments, and active fronthaul and cloud resources subject to communication, sensing, power, processing-capacity, and fronthaul constraints. A two-stage iterative algorithm based on Big-M reformulation, convex–concave programming, penalty-based relaxation, and structured discrete recovery is developed. Numerical results show that the proposed E2E framework reduces total power by up to 50% compared with transmit-power-only optimization and by approximately 11-17% compared with joint radio optimization under full coordination, while maintaining detection probabilities above 0.95. The results also reveal a fundamental implementation trade-off: FIS provides lower detector-processing complexity and higher detection performance, whereas PIS substantially reduces fronthaul requirements.
Read the full abstract

All authors Zinat Behdad, Özlem Tuğfe Demir, Ki Won Sung, Pei Xiao, Cicek Cavdar

Information Theory · Cross-listed from quant-ph

Phase Retrieval in $\mathbb C^4$ Requires Exactly Eleven Measurements

Determining the minimal number of intensity measurements required for phase retrieval in $\mathbb{C}^4$ has been a long-standing open problem. Prior to this work, the best-known results implied that this minimum was either $10$ or $11$. In this paper, we leverage characteristic classes and cohomology groups from differential topology to prove that no family of $10$ vectors in $\mathbb{C}^4$ possesses the phase retrieval property. Combining our lower bound with Vinzant's explicit eleven-vector construction establishes that the exact minimum is $11$. Our result yields a significant consequence for pure state quantum tomography, namely, a rank-one POVM on $\mathbb{C}^4$ requires exactly $11$ elements to be informationally complete for pure states. This further implies that three orthonormal bases are insufficient to uniquely distinguish all pure states in $\mathbb{C}^4$. Because four orthonormal bases are already known to be sufficient, we conclude that exactly four bases are required, thereby completely resolving the problem left in [C. Carmeli, T. Heinosaari, J. Schultz, A. Toigo, Eur. Phys. J. D].
Read the full abstract

Information Theory · Cross-listed from math.NT

Perfect $2$-codes over arbitrary alphabets

The classification of perfect $e$-codes over an arbitrary alphabet of size $q$ is complete for $e > 2$. In the case of non prime power $q$, it is conjectured that no perfect $2$-codes exist. We confirm this conjecture in a number of situations, including the case where $q=2^\alpha p^\beta$ with $p$ prime, $\alpha$ and $\beta$ positive integers, and either $\alpha \leq 20$, or $\alpha$ sufficiently large.
Read the full abstract

Wednesday 29 July

Information Theory

Assembly Theory and the Smallest Grammar Problem

Assembly theory (AT) quantifies complexity through the assembly index (ASI) – a metric proven equivalent to the size of the smallest straight-line program (SLP). While this equivalence links AT to data compression – a field shaped by decades of research – the practical efficacy of specific algorithms as ASI approximators remains largely unexplored. This study provides an empirical evaluation of eight compression algorithms, spanning grammar-based and dictionary schemes (CAs) across a dataset of 408 strings – comprising 368 synthetic strings (including max-complexity strings and strings with varying levels of symbol distribution balance, quantified by Shannon entropy) and 40 natural biological sequences (genomic and proteomic). We introduce Re-Pair T-NDR, a branch-and-bound tie-resolving variant of Re-Pair, providing a tighter upper bound on the ASI than the other CAs researched in this study. Increasing alphabet size extends the regime in which CAs closely track the ASI, delaying a “divergence point”, where a CA deviates from the optimal assembly path. The results establish compression algorithms as practical tools for ASI estimation.
Read the full abstract

Information Theory · Cross-listed from math.OC

Entropy-Smooth Convex Optimization Cannot Be Accelerated

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in $\ell_1$-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions $L$-smooth relative to negative von Neumann entropy on the spectrahedron of $d \times d$ Hermitian positive-semidefinite matrices with unit trace.
Read the full abstract

Information Theory

The Capacity Region of the Broadcast Channel with Non-Signaling Assistance

The capacity region of the $K$-user discrete memoryless broadcast channel is fully characterized when non-signaling (NS) assistance is available to the transmitter and all $K$ receivers. The NS-assisted capacity region is shown to coincide with Sato's region, i.e., the region defined by sum-rate bounds over all subsets of messages, where each bound corresponds to full cooperation among that subset of receivers under a worst-case joint channel law consistent with the marginal channels.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Classical and Quantum MacWilliams Transforms as Spin Kinematics

Spin is the hidden engine behind the zoo of MacWilliams transforms in weight enumerator theories - not only for qubits and qudits, but even for classical codes. From nothing more than a split into trivial and nontrivial errors, we kinematically derive the MacWilliams transform as a Wigner-$D$ rotation between two canonical bases. Within each classical and quantum theory, changing the length $n$ leaves the rotation untouched: the same element simply reappears at spin $n/2$. And at fixed $n$, changing the rotation axis simply moves between the various classical and quantum theories.
Read the full abstract

Information Theory · Cross-listed from math.CO

Combinatorial Bounds for Codes over Metric Spaces: Ramsey-Sidorenko Thresholds and Subgraph Counts

This paper investigates the relationship between coding theory and extremal combinatorics by representing codes in general metric spaces as independent sets in proximity graphs. We provide a generalized framework for the Gilbert-Varshamov (GV) bound applicable to codes over any finite metric space and explore the conditions under which global combinatorial parameters can force the existence of codes exceeding this bound. Central to our analysis is the introduction of Ramsey-Sidorenko and independence-forcing graphs. We establish density thresholds for various graph families and utilize the Karush–Kuhn–Tucker conditions to analyze entropy optimization in the Hamming case. Furthermore, we derive upper bounds on code sizes using fractional packings in vertex-transitive and nonedge-transitive graphs. Our findings demonstrate that local subgraph statistics alone are insufficient to surpass the GV bound in the Hamming case, suggesting that improvements must stem from large-scale structural properties of the space.
Read the full abstract

Information Theory

Entanglement-Assisted Quantum Locally Recoverable Codes: Characterizations, Bounds, and Constructions

Quantum locally recoverable codes (qLRCs) allow a single qudit erasure to be corrected by accessing only a small number of other qudits. Standard CSS and Hermitian constructions, however, impose dual-containing or self-orthogonal constraints on the underlying classical codes, thereby restricting the well-structured classical LRCs (cLRCs) that can be used to construct qLRCs. To relax these constraints, we introduce entanglement-assisted quantum locally recoverable codes (EAQLRCs) by assuming that halves of the pre-shared maximally entangled pairs are noiseless. We characterize sufficient support conditions on extended stabilizers under which entanglement-assisted stabilizer codes have locality $r$ and derive a CSS-like construction from two classical codes without imposing the ordinary dual-containing condition. We further establish an upper bound on locality and a Singleton-like bound for arbitrary CSS-like EAQLRCs, and characterize the pure codes attaining equality in the latter bound. These results yield a general framework for constructing optimal pure EAQLRCs from pairs of cLRCs. Applying this framework to $\ell$-intersection pairs of MDS codes and block parity-check matrices, we obtain two families of optimal pure CSS-like EAQLRCs with flexible parameters and nontrivial localities. To the best of our knowledge, these represent the first explicit families of EAQLRCs.
Read the full abstract

All authors Yang Li, San Ling, Zhenliang Lu, Gaojun Luo, Shixin Zhu

Information Theory · Cross-listed from cs.CC

Field Codes for Distributed Coupling Samplers and Certified Empirical Transport

In this paper, we formulate three communication tasks for empirical optimal transport: distributed coupling sampling, cost-evaluable coupling output, and scalar value-certified sampling. Our main result is a field-code compiler: any communicated transport field approximating an optimal empirical Monge map to error $\eta$ can be completed by sparse target-cell residuals into an exact-marginal value-certified sampler with scalar certificate $W_1(\mu,\nu)\leq U\leq W_1(\mu,\nu)+2\Delta$, where $\Delta$ is the public target-partition diameter. The certificate accuracy is controlled by $\Delta$ alone. The field error $\eta$ controls residual communication under a cell-margin condition; without a margin, $\eta$ alone does not bound residuals. We instantiate the compiler via adaptive local-affine and tensor-product spline codes with $d(m+1)^db$ field bits in the spline case, plus residual lists charged separately. For lower bounds, exact Gap-Hamming embeddings prove certified output is hard, including a smooth cell-packing diffeomorphism family requiring $\Omega(\varepsilon^{-2d/(d+4)})$ communication for any cost-evaluable, cost-certified, or value-certified protocol. The same gadgets admit zero-communication samplers, formally separating the sampler and certificate-bearing output models. These results identify the transport field as the right communicated object whenever a field code is available, primarily as a residual-sparsity tool.
Read the full abstract

All authors Hung Mai, Hai Nguyen, Luong Doan, Ngoc Vu, Khanh Nguyen, Nhung Duong, Tuan Do

Information Theory · Cross-listed from quant-ph

Reliability Functions of Quantum Soft Covering and Privacy Amplification via a Mixed-Order Rényi Divergence

In this paper, we introduce a novel mixed-order Rényi divergence and investigate its fundamental properties. Using this divergence, we define a family of mixed-order order-two Rényi mutual information and Rényi conditional entropy. We derive exact reliability functions of quantum soft covering and privacy amplification under the sandwiched Rényi divergence with order $\alpha\in[2,\infty)$. The former is jointly characterized by the sandwiched and mixed-order order-two Rényi mutual information quantities, while the latter is characterized by the corresponding conditional entropies. These results provide operational interpretations of the proposed mixed-order Rényi divergence. To the best of our knowledge, this is the first exact characterization of the reliability function for quantum soft covering.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Think Short, Defer Smart, Act, and Repeat: Calibrated Reasoning and Uncertainty-Aware Deferral for Edge LLM Agents

LLM agents following the ReAct paradigm are promising enablers of complex multi-step tasks, including multi-hop question answering, code generation, and control of physical AI systems. Yet, when deployed at the edge, they must tightly manage their reasoning budget while remaining reliable and deferring to a cloud-side model only when local uncertainty is too high to act safely. We propose Think Short, Defer Smart (TSDS), a framework that synergistically integrates a lightweight convergence probe, which halts on-device reasoning once the intended action has stabilized, with a perplexity-based deferral rule that escalates uncertain actions to a cloud-side model. Both mechanisms are jointly calibrated on end-to-end episode trajectories via a multi-objective Learn-Then-Test (LTT) procedure, providing simultaneous finite-sample guarantees on expected episode reward and cloud-call rate. We evaluate TSDS on four ReAct benchmarks spanning arithmetic reasoning (GSM8K), multi-hop question answering (HotpotQA), code generation (MBPP), and multi-step embodied planning (household robot), and compare against thought-calibration-only and calibrated-deferral-only standalone baselines. TSDS reduces per-episode thinking compute by 43%-65% over deferral-only baselines across HotpotQA, MBPP, and the household robot task, while maintaining certified reward and cloud-call rate guarantees.
Read the full abstract

Information Theory

Self-dual double cyclic codes over $\mathbb{F}_q$

This article focuses specifically on the study of self-dual double cyclic codes over a finite field $\mathbb{F}_q$. A self-dual double cyclic code is a double cyclic code that is equal to its dual. Structurally, a double cyclic code of length $(r,s)$ over $\mathbb{F}_q$ is a $\mathbb{F}_q[x]$-submodule of $\mathbb{F}_{q,r,s}:=\mathbb{F}_q[x]/\langle x^r-1\rangle\times\mathbb{F}_q[x]/\langle x^s-1\rangle$. Moreover, any double cyclic code of length $(r,s)$ over $\mathbb{F}_q$ is generated by two pairs of polynomials in $\mathbb{F}_{q,r,s}$. From the properties of the generating elements, we provide the necessary and sufficient conditions such that two pairs of polynomials in $\mathbb{F}_{q,r,s}$ generate a self-dual code. Furthermore, we examine the existence of self-dual double cyclic codes for some specific lengths: $(r,r)$; $(r,2r)$ and $(2r,r)$; and $(r,s)$, where $\gcd(r,s)=1$. For each case, we provide a construction method with some explicit examples over various finite fields. We also observe some connections between self-dual double cyclic codes and other classes of self-dual codes.
Read the full abstract

Information Theory

Upper bounds on the length of quasi-MDS codes

We study upper bounds on the length of $\mathbb F_q$-linear QMDS codes in the folded Hamming distance relative to their other parameters, especially the field size $q$. Via a correspondence between such codes and families of subspaces, we relate the length problem to that of upper bounding $1$-subspace packings with respect to the other parameters, especially the field size. Our main result is a reduction from these families to partial spreads, which allows us to import sharp bounds from finite geometry, including results of Drake-Freeman, Năstase-Sissokho, and Honold-Kiermaier-Kurz. As a consequence, we recover the Griesmer-type upper bound on the length of QMDS codes by Ball et al. and obtain tighter upper bounds in several parameter regimes.
Read the full abstract

Information Theory · Cross-listed from math.PR

An RDT based confirmation of Lehner's formula for Kronecker-Gaussian matrices

Remarkable breakthroughs [25,43] established the so-called strong asymptotic freeness between classical Gaussian random ensembles and their semicircular free counterparts. Along the same lines, the Lehner formula [31], associated with the free counterpart, precisely determines the spectral edges of Kronecker-Gaussian matrices. We here revisit and study this formula without the utilization of random matrix theory and spectral methods. In particular, relying on concepts utilized within Random Duality Theory (RDT) [45,46,51], we reconfirm Lehner's formula and effectively reprove the key asymptotic freeness results obtained via spectral methods in [25,43].
Read the full abstract

Information Theory

Polynomially Improved Lower Bounds for Trifferent Codes via Locally Sparse $3$-Uniform Hypergraphs

A ternary code is trifferent if every three distinct codewords have a coordinate in which their symbols are pairwise distinct. Let $T(n)$ be the maximum size of a trifferent code of length $n$. The classical Körner–Marton construction gives $T(n)\ge c_0(9/5)^{n/4}$ for an absolute constant $c_0>0$. We prove the polynomial strengthening $T(n)\ge c\sqrt{n}(9/5)^{n/4}$ for an absolute constant $c>0$. Our proof refines the outer-code step in the Körner–Marton concatenation. We encode non separating triples as edges of a $3$-uniform hypergraph, randomly thin its vertex set, and remove high-degree vertices together with all remaining Berge cycles of lengths two and three. The resulting locally sparse hypergraph admits a large independent set by a theorem of Verstraete and Wilson, producing the additional factor $\sqrt n$. Concatenation with the length-four Tetra code then yields the stated lower bound.
Read the full abstract

Tuesday 28 July

Information Theory · Cross-listed from eess.SP

Wireless Imaging for Low-Altitude Surveillance: A New Paradigm for ISAC Networks

The rapid growth of the low-altitude economy calls for integrated sensing and communication (ISAC) networks capable of robust flight monitoring. This article advocates wireless imaging as a unifying sensing paradigm that enables ISAC networks to function as comprehensive low-altitude guardians. We present a hierarchical imaging framework that enhances sensing capability from wide-area snapshot imaging to dynamic trajectory-aware imaging and target-centric fine-grained characterization. At the wide-area level, low-altitude sensing is reformulated as a spatial imaging problem, where distributed base stations and communication users collaboratively construct a holistic view of the aerial space. Building on this foundation, multi-frame dynamic imaging exploits temporal correlations to support robust trajectory tracking and prediction under mobility induced challenges such as occlusions. For security-critical scenarios, the framework further enables fine-grained imaging of flying and hovering uncrewed aerial vehicles, providing detailed characterization beyond conventional point-target abstractions. Additionally, we propose a novel evaluation metric named imaging coverage to examine the sensing fidelity of the proposed framework. Illustrative case studies demonstrate the potential of imaging in ISAC networks to support wide-area monitoring, motion-aware tracking, and fine-grained target analysis.
Read the full abstract

All authors Yixuan Huang, Jie Yang, Chao-Kai Wen, Shi Jin

Information Theory

The Code Distortion Problem

Two linear error-correcting codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$ are called linearly equivalent if there is a linear isometry mapping $\cal{C}_1$ to $\cal{C}_2$. In this work, we generalize the notion of linear equivalence and study the minimum distortion $\cal{D}(\cal{C}_1, \cal{C}_2)$ of a linear mapping between codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$, which quantifies how similar $\cal{C}_1$ and $\cal{C}_2$ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes $\cal{C}_1$ and $\cal{C}_2$. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where $\cal{D}(\cal{C}_1, C_2) = 1$ and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is $\mathsf{NP}$-hard to approximate to within any constant factor, and that it is in $\Sigma_2^P$. We also give a single-exponential-time $k^2$-approximation algorithm for CDP, where $k$ is the dimension of the input codes. Furthermore, we give a single-exponential-time $\big(\frac{2k + 1}{3})^2$-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix $0 \to 0$ "norm" on subspaces.
Read the full abstract

Information Theory

The Rate-Distortion-Deception Tradeoff

The problem of finding the optimal compression rate for a given random variable has been traditionally studied under two main constraints: distortion and perception. The distortion constraint enforces the fidelity of our reconstruction with respect to the observed realization of the random variable, while the perception constraint ensures that the reconstruction is close to a sample from the distribution of the random variable of interest. In this work, we explore the possibility of reconstruction, such that the reconstructed sample is still within a desired fidelity level with our original realization of the random variable, but at the same time, it resembles a sample from a different target distribution. We term this criterion as the deception constraint and find the fundamental tradeoffs of rate-distortion and deception.
Read the full abstract

All authors Semih Akkoc, Sahan Liyanaarachchi, Sennur Ulukus, Aylin Yener

Information Theory

Universal Individual-Sequence Prediction with a Primitive-Recursive Superpredictor

We study sequential prediction of individual binary sequences under zero-one loss. No computable master can compete on every sequence with all total computable predictors. We therefore consider rational-valued primitive-recursive forecasters, a broad syntactically enumerable class containing finite-state, context-based, and Prediction by Partial Matching (PPM) rules. We construct a computable probabilistic predictor with an explicit sublinear regret bound relative to every primitive-recursive forecaster on every individual sequence. We further prove that the PPM predictor is primitive recursive. Consequently, our predictor attains the infinite-past Bayes error on every Martin-Löf random realization of every computable stationary ergodic binary source. This optimality extends to finitely many independent such sources interleaved according to an arbitrary primitive-recursive schedule. Finally, we establish strict separations from finite-state prediction and from every fixed primitive-recursive predictor. keywords: Universal prediction, individual sequences, prediction with expert advice, primitive recursive functions, Kolmogorov complexity, PPM.
Read the full abstract

Information Theory

System-Aware Adaptive CSI Feedback via RL-Guided Autoencoder Switching in Multi-User MIMO System

This paper proposes a system-aware adaptive channel state information (CSI) feedback framework for massive multiple-input multiple-output (mMIMO) systems, aiming to dynamically optimize the trade-off between reconstruction fidelity and signaling overhead. While deep learning-based autoencoders (AEs) have enabled significant CSI compression, conventional fixed-ratio schemes fail to adapt effectively to non-stationary channel conditions. To address this limitation, we develop a reinforcement learning (RL)-driven control framework that operates over a bank of pretrained multi-rate AEs, each corresponding to a distinct compression ratio (CR). At each time step, a centralized RL agent selects the most suitable CR for each user based on observed channel conditions and system performance indicators. Distinct from conventional mean squared error (MSE)-centric designs, we introduce a system-aware reward formulation that jointly accounts for spectral efficiency via signal-to-interference-plus-noise ratio (SINR), feedback overhead constraints, and the computational cost of model adaptation. Simulation results on high-dimensional delay-domain CSI datasets demonstrate that the proposed RL-guided framework effectively balances the overhead-accuracy tradeoff and adapts to dynamic channel environments. The proposed method improves spectral efficiency and feedback efficiency compared with fixed compression schemes and adaptive baselines, while maintaining a modest computational and memory footprint. Averaged over different numbers of users and across all considered baselines, the proposed RL framework reduces the CSI feedback cost by more than 53.4%, improves the average downlink sum rate by 53.64%, and reduces the NMSE by 22.38%. These results demonstrate its ability to achieve a more efficient rate-accuracy-feedback tradeoff under dynamic wireless conditions.
Read the full abstract

All authors Maryam Ansarifard, Mohit K. Sharma, George Exarchakos, Kishor C. Joshi

Information Theory · Cross-listed from eess.SP

CORF-GS: Real-Time Wireless Radiance Field Reconstruction via Coupled Optical-RF Gaussian Splatting

Recent advances in 3D Gaussian Splatting (3DGS)-based wireless radiance field (WRF) reconstruction provide an efficient solution for wireless channel modeling. However, existing WRF reconstruction methods rely on pre-collected observations and offline optimization, and thus struggle to provide real-time channel knowledge. To bridge this gap, we propose CORF-GS, a real-time WRF reconstruction framework that processes sequential optical and radio frequency (RF) keyframes. Specifically, CORF-GS constructs a unified Gaussian representation for optical and RF with shared geometry and modality-specific appearance, allowing high-resolution optical images to provide structural priors for WRF reconstruction. When a new keyframe arrives, CORF-GS first employs optical-guided Gaussian sampling to densify the WRF in under-represented regions. Since light and radio waves may respond differently to the same object surfaces due to wavelength mismatch, relying solely on optical guidance may neglect RF-informative areas. Therefore, CORF-GS performs coupled optical-RF optimization to jointly refine the shared Gaussians. Compared with the existing two-stage training pipelines, this prevents WRF from passively adapting to a frozen optical geometry and encourages the shared Gaussians to adapt to both optical structures and RF power distributions. Simulations show that CORF-GS achieves state-of-the-art RF spectrum synthesis quality and reduces the reconstruction time by $6.4\times$ compared with existing WRF methods.
Read the full abstract

All authors Jinya Zhang, Jiajia Guo, Chao-Kai Wen, Shi Jin

Information Theory

Bayesian-Guided Cooperative RL Beamforming for Wireless Adversarial User Detection

In next-generation wireless networks, communication systems are expected to go beyond simple data transmission and simultaneously provide high data rates, efficiency, and security. This requirement has motivated the extensive adoption of machine learning methods to develop intelligent and real-time network management frameworks, enabling the system to continuously monitor and react to channel variations and user behavior while maintaining efficient information delivery. In this context, the integration of machine learning with beamforming enables adaptive and data-driven beam direction selection, improving both the efficiency and security of wireless links. In this work, a 3GPP-based system model is first implemented under a no-attacker scenario, and an exhaustive search is employed as a reference to identify the best beamforming configurations. The proposed framework is then evaluated in the presence of an attacker and under different network scalability conditions. We demonstrate that the reinforcement learning-based approaches, namely Q-learning and SARSA (State-Action-Reward-State-Action), consistently outperform random selection in terms of total channel capacity, attacker detection accuracy, and performance stability. Among the evaluated reinforcement learning methods, Q-learning achieves the best overall trade-off between detection accuracy and computational efficiency. Our results indicate that the proposed framework provides a stable, scalable, and effective solution for joint beamforming and security-aware decision-making in dynamic and adversarial wireless environments.
Read the full abstract

Information Theory

Learned Blockwise Port Activation for Real Time Beamforming in Fluid Antenna Arrays

Fluid antenna arrays (FAAs), support multiuser downlink transmission by activating a subset of reconfigurable ports. The activation mask jointly determines the effective channel and the sparse radiating aperture, which requires a balance among sum rate, sidelobe suppression, hardware constraints, and online complexity. Channel driven selection can cluster active ports and increase sidelobes, whereas sidelobe oriented synthesis is typically channel independent and can sacrifice sum rate. This paper proposes learned blockwise port activation (L-BPA), for real time sidelobe aware FAA downlink beamforming. L-BPA activates a fixed number of ports in each aperture block, which supports grouped switching hardware and limits port clustering. A lightweight convolutional network scores ports using multiuser channel features, port coordinates, and user power statistics. Training combines blockwise straight through masks with a differentiable peak sidelobe level (PSLL), surrogate. During inference, learned scores are combined with multiscale geometric repulsion, followed by regularized zero forcing precoding over the reduced effective channel. L-BPA reduces the average PSLL by 3.26 dB relative to uniform sparse activation while achieving a slightly higher sum rate. It also reduces the PSLL by 8.13 dB and 10.10 dB relative to greedy and gain based selection, respectively, without iterative online search.
Read the full abstract

All authors Yuanhui Wu, Zhentian Zhang, Hanjiang Hong, Hao Jiang, Zaichen Zhang, Kai-Kit Wong, Yin Xu, Wenjun Zhang