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)

Sunday 4 October

Information Theory

Order-Optimal Coded Caching With File and Demand Privacy

We study coded caching with joint file and demand privacy: each user recovers its requested file while learning nothing about the remaining files and the other users' requests jointly. Let $N$ and $K$ be the numbers of files and users, and let $M$ and $R$ denote the cache memory and delivery rate, both normalized by the file size. For every $N,K\ge2$ and every feasible cache size, we give a scheme whose worst-case delivery rate is at most $9/2$ times the optimum. To reduce the memory used for file shares, the scheme secret-shares $N-1$ differences relative to a reference file. Cached masks supply the correction needed to recover the requested file from its difference. For each integer $t\in\{0,\ldots,K-1\}$, the scheme achieves $M=1+(N-1)t/(K-t)$ and $R=K/(t+1)$. To lower-bound the delivery rate, we compare the joint cache entropy of user groups under alternative demand vectors, using one fixed user's privacy constraint. Two choices of groups determine the optimal delivery rate up to constants at the scale $\min\{K,1+(N-1)/(M-1)\}$ for $M>1$. At $M=1$, the exact optimum is $K$. A complementary bound on joint broadcast entropy gives the minimum memory for unit delivery rate, $1+(N-1)(K-1)$, and the exact tradeoff on an interval ending at that memory. All schemes and bounds apply to repeated as well as distinct requests.
Read the full abstract

Information Theory

Nonlinear Posterior-Mean Feedback Codes for AWGN Channels

Feedback can improve the reliability of communication over additive white Gaussian noise (AWGN) channels. Classical feedback codes are interpretable, or easy to understand, but often rely on linear estimation, while deep-learned feedback codes can achieve strong performance but require many learned parameters and are often black boxes that are difficult to interpret. In this work, we propose a new posterior-mean feedback coding framework for AWGN channels with feedback. The proposed scheme uses posterior-mean refinement to construct nonlinear feedback codes under both noiseless passive feedback and noisy active feedback, with maximum a posteriori (MAP) decoding at the receiver. This scheme is analytically described, but a few learned parameters related to power allocation, and hence we consider this an “interpretable,” or human-understandable code. We further develop a projection-based design to improve robustness under noisy feedback and support larger message sizes. Numerical results show that the proposed schemes achieve strong finite-blocklength performance and outperform several analytical and learned feedback coding baselines, while using only a small number of learned design parameters.
Read the full abstract

All authors Yingyao Zhou, Natasha Devroye, Milos Zefran, Gyorgy Turan

Information Theory · Cross-listed from eess.SP

One-Shot Beam Tracking for Stacked Intelligent Metasurfaces-Assisted LEO Broadcasting

This letter develops a physics-informed one-shot beam tracking method for stacked intelligent metasurface (SIM)-enabled low-Earth-orbit (LEO) links with $K$ users and an $L$-layer SIM with $N$ meta-atoms per layer. The predictable orbital motion is propagated through the line-of-sight (LoS) geometry to forecast the finite-interval variation of the user signal-to-noise ratio (SNR) profile, and an analytical multilayer Jacobian relates this variation to the $LN$ SIM phase coefficients. Beam tracking is formulated as normalized SNR-profile preservation and solved through a single regularized Gauss–Newton correction that requires one Jacobian evaluation and a $K\times K$ linear solve, thereby avoiding iterative reoptimization. A tracking-error bound separates the regularization residual from the nonlinear Taylor remainder and establishes a second-order local error under a full-row-rank Jacobian. Numerical results show that the proposed method retains approximately $94\%$ and $92\%$ of the iterative-reoptimization rate for $L=2$ and $L=4$, respectively, while running about $350\times$ and $260\times$ faster at $N=225$, and confirm the predicted second-order residual error behavior.
Read the full abstract

All authors Chandan Kumar Sheemar, Giovanni Iacovelli, Sourabh Solanki, Wali Ullah Khan, Symeon Chatzinotas

Information Theory · Cross-listed from cs.AI

The Functional Structure of Post-Compression Recovery in Low-Rank LLMs

Different low-rank compression methods can produce compressed LLMs that respond differently to the same post-compression recovery procedure, and relative advantages observed between methods at the compression endpoint may shrink, grow, or even reverse after recovery. We ask whether this recovery heterogeneity reflects functional structure beyond scalar loss evolution, and how that structure evolves throughout recovery. Our results establish that this heterogeneity reflects a reproducible compression-induced functional structure, which we formalize as recovery pressure. To characterize this structure consistently throughout recovery, we develop a standardized functional characterization within each backbone that is applicable across heterogeneous low-rank methods. The primary backward characterization reveals reproducible module-wise structure across independent probes, while a complementary forward-only characterization recovers related structure without loss or backpropagation. We further find that recovery pressure measured at the endpoint is associated with subsequent recovery response; during recovery, its module-wise structure is reorganized non-uniformly, and localized updates induce distributed responses beyond directly updated modules. Further evidence indicates that tracking this evolving structure provides a complementary functional view of recovery progress alongside scalar loss.
Read the full abstract

All authors Zishan Shao, Liang Tian, Georgiy Zemlevskiy, Kangning Cui, Lixun Zhang, Yixiao Wang, Ting Jiang, Jinhee Kim, Yixuan Chen, Rui-Feng Wang, Fan Yang, Hai Li, Yiran Chen

Information Theory · Cross-listed from quant-ph

Minimax Quantum State Tomography in a Known Trace-Distance Ball

We study quantum state tomography when the unknown state lies in a trace-distance ball of radius $R$ around a known reference state $\rho$. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write $\Gamma=d(\mathrm{Tr}\sqrt\rho)^2+d^2R$. For $d\ge2$, $0<R\le1$, and $n\ge1$ copies, the expected risk is $\Theta(\min\{R,\sqrt{\Gamma/n}\})$. At failure probability $0<\delta\le1/3$, the minimax confidence radius is \[ \Theta\!\left(\min\left\{R,\sqrt{\frac{\Gamma+\log(1/\delta)}{n}}\right\}\right). \] For $\varepsilon\le c_0R$ with a universal $c_0>0$, the copy complexity is $\Theta((\Gamma+\log(1/\delta))/\varepsilon^2)$. For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.
Read the full abstract

Information Theory

Modulation and Integration in a local processor having input from two distinct sources

By making use of partial information decomposition, we analyse information transmission through a local processor which receives two streams of integrated inputs. We revise previously stated conditions for contextual modulation that are based on the components of partial information decomposition, and introduce a condition for the presence of signal integration. Exact results are obtained for information-theoretic measures and the components of partial information decomposition using the Ibroja method. A general class of activation functions is considered along with a particular divisive normalisation transfer function. These results are applied with several activation functions, of additive, multiplicative, subtractive and divisive forms, with graphical illustration, and the conditions for modulation and integration are tested in each case. The revised information-theoretic conditions are also applied to noisy data obtained from a realistic simulation of a model layer 5b pyramidal cell in three distinct regimes defined by experimental design and characterised by the values of the input basal and apical amplitudes. Evidence for driving basal input with modulating apical input, driving apical input with modulating basal input, and of apical-basal signal integration is presented.
Read the full abstract

Information Theory

Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing

Approximate Message Passing (AMP) algorithms are attractive as they are computationally efficient and simultaneously admit a precise characterization in terms of the low-dimensional "state-evolution" recursion. In this work, we establish quantitative universality for AMP with centered rank-one sensing matrices $Z_i=(x_ix_i^\top-I_d)/\sqrt d$, where $x_i$ are independent standard Gaussian vectors. These matrices arise in quadratic regression and learning quadratic neural networks. Their normalized vectorizations have isotropic covariance in dimension $p=d(d+1)/2$, but strongly dependent coordinates. For linear observations with Gaussian noise and prescribed smooth, bounded spectral denoisers, we compare rank-one sensing with a covariance-matched isotropic Gaussian ensemble. At a fixed iteration horizon, with $n\leq Cp$ and uniform bounds on the normalized signal energy, initialization, coefficients, and first four denoiser derivatives, normalized signal overlaps, cross-time overlaps, and smooth linear spectral statistics differ by $O(d^{-1/2})$ in every fixed $L^m$. This yields universality of the normalized mean-squared error, fixed spectral moments, and empirical spectral distributions. Whenever the Gaussian observables admit a joint state-evolution limit, the same predictions hold under rank-one sensing. The proof uses columnwise Lindeberg replacement, leave-one-out analysis, smooth spectral expansions, and high-moment concentration. For prescribed smooth spectral denoisers, the result establishes the AMP universality conjectured by Maillard et al. (arXiv:2408.03733).
Read the full abstract

Information Theory

Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes

We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.
Read the full abstract

Information Theory

Improved Bounds on the Ingleton Score of Four Random Variables

For four finite discrete random variables, we prove that the negative of the Ingleton expression, divided by the joint entropy, is at most $19/124 \approx 0.15323$, improving the previously reported upper bound $3/19$ by $11/2356$. The proof uses a copy program with four copy steps and six auxiliary variables, certified by exact rational linear-programming certificates. We also show that two published information inequalities, due to Dougherty-Freiling-Zeger and Csirmaz, imply the bound $5/32$ by an explicit nonnegative combination with Shannon inequalities, and that $5/32$ is the exact optimum both of the union of the three published inequality catalogues considered here and of the full copy-lemma extensions of all 213 distinct copy programs occurring in them. The new program is not among these programs, and the bound $19/124$ remains optimal when all of them and all catalogue inequalities are added. Ancillary files provide the parsed catalogues, exact primal and dual certificates, exact extension certificates, and verifiers that use only the Python standard library.
Read the full abstract

Information Theory

Secure Multi-Access Coded Caching: A Lifting Approach

We construct secure cyclic multi-access coded caching schemes by re-encoding the caches of a secure single-access scheme and reusing its multicast message unchanged. For a library of $N$ files, each of $K$ users reads $L<K$ consecutive shared caches and must recover its requested file while learning no information about the other files. Starting from a parent scheme with a cyclic representation of its cached symbols, the transformation lets each access window recover the corresponding parent-cache symbols and, conditioned on them, learn nothing about the remaining symbols. A deterministic Pascal-window encoder handles symbols whose consecutive appearances span at least $L$ users. A randomized complement-dual encoder handles shorter spans. Over a suitable finite field, these encoders attain the exact minimum per-block storage for every input length in the block-separable, parent-preserving class. Applying the transformation to two secure single-access schemes gives an achievable memory-rate family for $N,K\ge2$ and $1\le L<K$, including the exact rate-one cache size $(N-1)(K-1)/L$. Using converse bounds for arbitrary secure multi-access schemes, we prove approximation guarantees for the achievable family and give a proof of the exact $L=K-1$ tradeoff.
Read the full abstract

All authors Han Fang, Qinyi Lu, Nan Liu, Wei Kang

Information Theory · Cross-listed from physics.comp-ph

A Contrast-Source Inversion Scheme Based on Stochastic Optimization and Plug-and-Play Regularization

An electromagnetic inversion scheme that integrates stochastic optimization (STO) and plug-and-play (PNP) regularization into contrast-source inversion (CSI), termed STO-PNP-CSI, is developed. Standard CSI solves for the contrast source vector of every transmitter at each iteration, which is expensive in a multi-transmitter configuration. STO instead solves for only one randomly selected contrast source vector per iteration, which reduces the per-iteration cost and can help the inversion escape poor local minima and saddle points. The resulting loss of information, however, increases the ill-posedness of the inversion. To counter this, the Swin-Conv-UNet (SCUNet) denoiser is plugged into the CSI scheme as an implicit regularizer, supplying a learned prior that is stronger than conventional hand-crafted ones and stabilizes the reconstruction. The proposed STO-PNP-CSI is applied to both synthetic and experimental data. The results show that it yields accurate reconstructions at substantially lower computational cost than CSI, including under strong nonlinearity and measurement noise.
Read the full abstract

Information Theory

Secure D2D Coded Caching under Radius-Limited Connectivity via Lifting

Secure device-to-device (D2D) caching requires users to generate delivery signals from their own caches and to recover their requested files without learning the other files. We construct schemes that meet both requirements when communication is limited to nearby users. The network consists of $K$ users on a cycle, a library of $N$ independent files, and a reception radius $r$. Delivery uses one round of noiseless orthogonal local broadcasts, with no server transmission. Each user's cache has capacity $M$ file units. An outer secret-sharing code assigns file shares to senders, and a secure local caching scheme at each sender delivers the requested shares. The cache budget includes the sender's library representation, random state, and delivery keys. We prove that each receiver's cache and all audible broadcasts jointly reveal no information about nonrequested files, despite the dependence between the outer shares. The converse counts transmissions crossing a contiguous user block and uses secrecy to remove one user's observation from the entropy bound. Let $h=2r$ and $K\ge h+1$. The private coded caching (PCC) instantiation attains the minimum peak sum load $K/h$ for every $M\ge Nh$ when $N>1$. For $N\ge K$, its memory-sharing envelope is within a factor $15$ of the optimum throughout $M\in[N/h+2,Nh]$. We also apply lifting without secrecy constraints, achieving the optimal load on $M\in[hN/(h+1),N]$ and a factor-$9/2$ guarantee on $M\in[N/(h+1),N]$ when $N\ge K$.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Quantum codes in the Lee metric

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary “helical repetition codes” have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.
Read the full abstract

All authors Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu, Victor V. Albert, Andrew Lucas

Information Theory · Cross-listed from quant-ph

Entanglement-of-formation potentials for feedback-assisted classical communication and randomness distillation

We develop entanglement-of-formation potentials for feedback-assisted classical communication and one-way randomness distillation. For a finite-dimensional quantum channel without initial shared entanglement, an exact amortization theorem bounds the increase of message information plus entanglement remaining across the communicating laboratories. This proves a classical-feedback capacity bound using a mixed-convex-roof expression previously studied by Winter and Yang in the context of potential capacities. We determine the capacity of flagged mixtures of noiseless and entanglement-breaking channels, improve a published depolarizing-channel converse, and evaluate the new bound exactly for the amplitude damping channel. A state analogue gives a finite-blocklength upper bound on the net shared randomness obtainable with one-way classical communication. Amplitude-damping Choi states provide exact benchmarks, while a full-rank generalized amplitude-damping Choi state demonstrates a useful improvement where we do not evaluate the operational rate exactly. We also distinguish one-way from two-way randomness distillation: a two-round weak-measurement protocol strictly exceeds the exact one-way rate of every nontrivial qubit isotropic state. The protocol preserves quantum side information during its first decoding and extracts additional randomness in the reverse direction. This shows why the one-way state potential is not a general two-way converse. Together, these results establish a common entanglement-based approach to sharper communication and randomness bounds, while revealing how retained quantum correlations enable two-way distillation to surpass one-way limits.
Read the full abstract

Saturday 3 October

Information Theory

Scalable Distortion-Aware Clustering for Fronthaul-Limited Cell-Free MIMO Networks

This paper studies distortion-aware clustering for uplink fronthaul-limited cell-free MIMO networks employing maximum ratio combining (MRC). While MRC is appealing for its low-complexity, its performance is limited by interference, fronthaul distortions, and channel imperfections. This motivates clustering strategies that compensate for these impairments through coordination of access points. Since instantaneous small-scale fading-based optimization is not scalable in large systems, and is impractical due to frequent channel variations, we instead optimize an objective depending only on large-scale fading coefficients. To this end, asymptotic analysis is used to derive deterministic equivalent expressions for the average network sum rate, with focus on quantization distortion, leading to a quadratic-over-linear objective. Although maximizing such an objective under binary constraints is non-convex, we exploit its structure to develop a polynomial time scheme that attains the global optimum. Numerical results show that the proposed clustering method provides performance gains over improved variants of existing literature, and remains competitive with the small-scale fading-based global optimum obtained via exhaustive search.
Read the full abstract

All authors Zehua Li, Raviraj Adve, Israfil Bahceci, Yahia Ahmed

Information Theory · Cross-listed from eess.SP

Toward a Lean Formalization of Analog Computing with Microwaves

Analog computing with microwave signals can perform linear transformations directly in the analog domain, as the signals propagate through a microwave network. A fundamental question is which transformations can be computed with a given set of microwave components. In our previous work, we answered this question for networks of hybrid couplers and phase shifters by deriving a necessary and sufficient condition on the transformations these networks can compute, and we showed that the discrete Fourier transform (DFT) satisfies it. In this paper, we take a first step toward the formalization of analog computing with microwaves in Lean, a programming language and proof assistant that is increasingly adopted in mathematics. We formalize the considered components, their series and parallel connections, and the class of networks they can implement. Then, we formally prove the necessary and sufficient condition characterizing these networks, as well as the implementability of the DFT of any size power of two. All proofs are checked by the Lean kernel, and the code is openly available at: https://github.com/matteonerini/formalizing-analog-computing.
Read the full abstract

Information Theory

Learning OTA: A Unified Framework for Edge Sensing, Computation, and Communication

Most federated learning (FL) studies implicitly assume that training data is readily available at participating edge devices. In practice, this data must first be acquired through heterogeneous sensors with potentially different measurement modalities, and the quality and cost of this acquisition process can directly affect the learning performance. This dependence creates a coupled relationship among sensing, computation, and communication, necessitating a system model that captures their joint effect on resource efficiency and learning accuracy. This paper develops such a unified treatment for an over-the-air (OTA) FL system in which each device configures its sensing modality, power, resolution, and sample size, with aggregations conducted OTA at the server. We derive models for sensing noise, energy consumption, latency, and OTA aggregation distortion, and establish a non-convex convergence bound quantifying how these factors influence the global model trajectory. Guided by this analysis, we formulate a per-round optimization that balances energy, latency, and learning quality under physical device constraints. The resulting mixed optimization is addressed through an alternating procedure with closed-form and one-dimensional updates for continuous variables and a lightweight discrete search. Numerical experiments corroborate the advantage of jointly optimizing sensing, computation, and communication decisions.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Stabilizer codes over general phase spaces

We develop a theory of stabilizer codes whose stabilizer groups consist of commuting qudit Paulis, oscillator displacements, and/or planar-rotor displacements. We consider codes whose stabilizer groups form generalized lattices in quantum phase space, a condition that guarantees a finite logical dimension. We construct oscillator-rotor, rotor-qudit, and oscillator-rotor-qubit codes that cannot be decomposed into separate subsystems by generalized Clifford transformations. We also introduce an oscillator-qubit code arising from a partially lifted Golay code, where Construction A is applied to half of the Golay code coordinates. We derive analytical forms of logical operators from the symplectic dual lattice, determine Clifford-Gaussian gates from lattice symmetries, show that the code dimension equals the covolume of the stabilizer lattice, and organize the syndrome subspaces into a vector bundle. Our technique builds on earlier non-commutative geometric results by Rieffel, but it can often be interpreted simply as concatenating a given stabilizer code with a Gottesman-Kitaev-Preskill (GKP) code, applying conventional lattice-theoretic results, and unconcatenating. We formulate distances, optimal decoding, and quantum weight enumerators, recovering the Pauli, qudit, and GKP versions together with known MacWilliams identities. We construct finite-energy codewords whose encoding is an isometry up to an error exponentially small in the inverse damping parameter.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Quantum-State Oblivious Transfer over Quantum Erasure Channels

We study quantum-state oblivious transfer over the quantum erasure channel under information-theoretic security guarantees. Specifically, Alice holds two quantum systems, Bob wishes to recover one of them, and the parties have access to independent channel uses and authenticated public classical communication, with no initial shared entanglement. We consider both honest-but-curious and malicious behavior. We establish finite-blocklength converse and achievability bounds, which match in the honest-but-curious setting. The malicious setting construction combines interactive hashing with tests of whether Bob received selected channel outputs, and distributes each input across several qubits so that erasures conceal an entire input from a dishonest receiver, even when the inputs are entangled with an external reference. We also derive fixed-error asymptotic expansions and show that both malicious and honest-but-curious settings have the same capacity.
Read the full abstract

Information Theory

Fluid Antenna Secure Channel-driven Constellation (FASCC): a Physical Layer Security approach

Fluid antenna systems (FAS) have recently emerged as a promising technology for future wireless networks due to their ability to access a large number of channel realizations using a single radio-frequency chain. This capability creates new opportunities for physical-layer security beyond conventional beamforming and artificial-noise approaches. In this paper, we propose a novel Fluid Antenna Secure Channel-driven Constellation (FASCC) framework for downlink communications, in which information is conveyed through channel-domain constellation points generated by FAS port selection and phase adaptation. Two complementary FASCC schemes are developed, depending on the availability of eavesdropper's channel state information. Numerical results demonstrate that the proposed FASCC framework achieves significant secrecy gains in terms of bit error rate and mutual-information secrecy performance, even when Eve is significantly closer to the base station than Bob.
Read the full abstract

Information Theory · Cross-listed from cs.LG

Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy

Best arm identification under differential privacy is a pure-exploration problem in which both statistical efficiency and privacy protection must be achieved simultaneously. We study fixed-budget best arm identification for bandits under pure $\epsilon$-differential privacy, where the learner must recommend an arm after a prescribed sampling budget while protecting the full transcript. We prove that the optimal exponential decay rate of the error probability is upper bounded by an instance-dependent privacy-aware transportation exponent that differs from the analogous quantity used to characterize the stopping time in fixed-confidence analysis by Jourdan and Azize [2025]. Guided by this exponent, we propose AO-Pri-BAI, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min–max interaction between hard alternatives and arm allocations. We prove that AO-Pri-BAI satisfies pure $\epsilon$-differential privacy. We also establish that the exponent of the failure probability of AO-Pri-BAI matches the privacy-aware benchmark. Numerical studies show that even in the non-asymptotic setting, AO-Pri-BAI outperforms benchmark algorithms on various instances, complementing the theoretical analyses.
Read the full abstract

All authors Keqin Chen, Jie Bian, Yulian Wu, Vincent Y. F. Tan

Information Theory

Plotkin-type Bound on Function-Correcting Codes for Monomial Mappings

Function-correcting codes, recently introduced by Lenz et al.\ (2023), provide a framework for the receiver to provide a higher level of protection against channel errors than the level of protection for messages. In this paper, we derive a generalised Plotkin-type bound on the redundancy of FCCs under the Hamming metric for arbitrary functions over finite fields. The proposed bound recovers the classical Plotkin bound for classical error-correcting codes as a special case. We further obtain explicit Plotkin-type bounds for linear functions, Hamming-weight functions, and Hamming-weight threshold functions. In addition, we study FCCs for monomial mappings $f(x)=x^n$ over $\mathbb{F}_{q^k}$, which are widely utilised in coding theory, cryptography, and finite geometry, and derive an explicit Plotkin-type redundancy bound.
Read the full abstract

Information Theory · Cross-listed from eess.SP

QoS-Constrained Resource Pattern Design for V2X-ISAC Systems

Integrated sensing and communication (ISAC) has emerged as a promising approach for vehicle-to-everything (V2X) systems by enabling communication and sensing over shared radio resources without additional installation of dedicated sensors. However, candidate resources may experience different communication qualities due to varying channel conditions and resource contention, which should be considered when designing sensing resource patterns. In this letter, we propose a quality-of-service (QoS)-constrained resource pattern selection framework that jointly considers communication reliability and sensing performance. The sensing objective is formulated based on the Fisher information matrix for joint range and velocity estimation, while a minimum packet reception ratio (PRR) is imposed as the communication QoS constraint. To avoid the complexity of exhaustive search, a greedy selection algorithm with one-swap refinement is developed. Simulation results show that the proposed method improves sensing performance over conventional resource patterns while satisfying the PRR requirement and achieves performance close to the exhaustive-search optimum and sensing-only optimum.
Read the full abstract

All authors Hanyoung Park, Gangmin Kim, Yoo-Seung Song, Ji-Woong Choi

Information Theory

Timely Persuasion with Opposing Senders: When Does Competition Help the Receiver?

Status updates let a receiver track a changing process, but a sender that controls when they are sent can steer the receiver's estimate without misreporting. We study competition between two such senders with opposing preferences, who report on a binary continuous-time Markov chain using state-dependent Poisson rates under individual budgets. The receiver follows the reports through a zero-order-hold estimator only if this yields at least the long-run weighted correct-estimation utility of a prior-based default estimate. We model the interaction as a Stackelberg game in which the sender favored by this default leads, the opposing sender follows, and the receiver then selects its estimator. We characterize the pure-strategy equilibria in closed form. When the follower can obtain positive utility against a silent leader, limited state-$0$ reporting by the leader merely frees part of the follower's budget for state-$1$ reports, so every optimal leader policy is either silence or full-budget state-$0$ reporting, depending on explicit budget thresholds. A single sender with the same total budget leaves the receiver at its default utility, whereas the full-budget intervention outcome makes the receiver's participation constraint slack and strictly improves its utility. At the intervention threshold, silence and full-budget intervention yield identical sender payoffs but different receiver utilities. Numerical results illustrate these regimes and compare equilibrium performance with a receiver-optimal reporting benchmark.
Read the full abstract

Information Theory

Identification and Recovery of Linear Dynamics from Partial Trajectories

We study the joint recovery of an unknown system matrix $A\in\mathbb R^{n\times n}$ and a rank-$r$ initial-state matrix $X_0\in\mathbb R^{n\times m}$ from partial observations of the state matrices $A^tX_0$, for $t=0,\ldots,T$. Each trajectory is observed at a fixed set of state coordinates, which may differ across trajectories. We derive necessary conditions for identifiability, including obstructions arising from incomplete spatial coverage and insufficient dynamical span, as well as lower bounds on the number of observations. We then characterize the Jacobian of the measurement map, account for the intrinsic symmetry of the low-rank factorization, and establish a rank-certificate principle yielding generic local identifiability. When the trajectories whose initial states form a basis of $\operatorname{range}(X_0)$ are fully observed, we obtain necessary and sufficient rank conditions for global recovery, together with explicit reconstruction formulas. We formulate the joint recovery problem as a nonlinear least-squares problem over the system matrix $A$ and the low-rank factors of $X_0$, and solve it using Adam. Numerical experiments on synthetic and real-world data evaluate the recovery performance under different spatial sampling rates and observation horizons.
Read the full abstract

Friday 2 October

Information Theory · Cross-listed from cs.CR

Symmetric Cryptography via Dirichlet Convolution

We discuss a new symmetric-key cipher for digital data encryption. Its implementation is fast, memory efficient, and resilient against classical, AI-assisted, and quantum attacks. Let $x$, $k$, and $c$ be elements of a finite abelian group $G$ with operation $+$ and neutral element $0$. Suppose one is given ciphertext $c=x+k$. Retrieving the plaintext $x=c-k$ from the ciphertext is trivial when the key $k$ is known. Without the key, however, recovering $x$ amounts to a blind search. Even if an efficient criterion were available for identifying the plaintext among all group elements, the average number of trials would remain prohibitively large when the group is sufficiently large. The challenge in constructing a practical cryptosystem is therefore to identify a sufficiently rich group $G$, together with efficient algorithms that enable an immersion of real digital data into $G$ and efficient evaluation of the group operations. The proposed cipher is based on generalized Dirichlet convolution over finite fields. We investigate its security against plaintext attacks from an information-theoretic perspective. The nonlocal structure of Dirichlet convolution naturally permits plaintext salting, providing protection against plaintext attacks while allowing controlled key reuse. We establish perfect masking properties over finite fields and prove that the resulting cipher achieves information-theoretic security under key reuse when the underlying arithmetic is carried out in $\mathbb{F}_p$ with $p>2$. For arithmetic over $\mathbb{F}_2$, some information leakage remains, leading to a finite key-reuse budget.
Read the full abstract

All authors Artur Sowa, Elias Hassani Sangani, Francis Bui, Grant Harris, Jonathan Norton

Information Theory

RIS Aided Multi-Way Communication Systems based on SIC Decoding Techniques

This work considers reconfigurable intelligent surface (RIS) aided multi-way communication systems employing QPSK. The objectives of such system is to allow multiple users to exchange information, exploiting the full-duplex capabilities of RIS. The system under consideration comprises $K$ user terminals and an RIS with $N$ reflective elements. Each user terminal is equipped with one transmit and $M$ receive antennas. To mitigate inter-user interference caused by the full-duplex operation of the RIS, three successive interference cancellation (SIC) techniques are considered. We investigate three SIC ordering methods: $1)$ descending channel variances, $2)$ increasing mean square error, $3)$ optimization approach which maximizes the combined channel gain within the system. The bit error rate (BER) performance of these three SIC methods are evaluated using extensive Monte-Carlo simulations for different numbers of RIS elements, ranging from 4 to 64, and a varying number of transmitting users, ranging from 1 to 5. Additionally, an RIS phase shift optimization method for RIS with reflection elements of varying amplitudes is considered. In this case the previous SIC optimization technique is adapted to address phase-dependent amplitudes in RIS reflection elements. Simulation results indicate that in both ideal and varying amplitude scenarios, when the number of RIS elements is small, SIC with ordering based on increasing mean square error achieves the best BER performance. However, as the number of RIS elements increases, SIC ordering based on the optimization method achieves the best BER performance.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Latent Score-Based Bayesian Cramér-Rao Bound Estimation for High-Dimensional Imaging Systems

We propose a data-driven framework for estimating the Bayesian Cramér-Rao bound (CRB) in high-dimensional imaging systems with complex, analytically intractable priors. Direct CRB computation is challenging in this setting due to the need to model the prior score and to form and invert the Bayesian Fisher information matrix in very high dimensions. To address these issues, we first reformulate the inverse problem in the latent space of a pre-trained variational autoencoder, thereby dramatically reducing the dimensionality of the bound estimation problem while preserving the spatial structure of the images. The Bayesian CRB is formed in this latent space and mapped back to the native parameter space using a change-of-variables formula. Second, to learn the latent prior score, we introduce a new sliced score matching objective defined in a Bochner space endowed with an $H^1(\Omega)$ Sobolev norm in space. This "Bochner-space sliced score matching" objective is consistent with standard sliced score matching, but penalizes errors in the spatial gradients of the score, suppressing high-frequency artifacts that otherwise contaminate the resulting CRB estimates. We validate the approach on a stylized quantitative photoacoustic computed tomography (qPACT) breast imaging problem with over one million unknown parameters, using a foundation-model autoencoder derived from Stable Diffusion. The proposed method yields stable, artifact-free Bayesian CRB estimates that reflect the highly non-Gaussian structure of the learned prior and reveal the substantial impact of the prior on the relative performance of competing qPACT design schemes.
Read the full abstract

All authors Evan Scope Crafts, Thomas Wynn, Seonyeong Park, Mark Anastasio, Umberto Villa

Information Theory · Cross-listed from math.CO

An Improved Upper Bound for Recovering Pairs

We prove that every recovering pair $(\mathcal{A},\mathcal{B})$ of nonempty families of subsets of an $n$-element set satisfies $$|\mathcal{A}||\mathcal{B}|\le\left(\frac{223949}{100000}\right)^n=(2.23949)^n.$$ A result of Mond, Souza and Versteegen, combined with the sharp $(9/4)^n$ bound of Fang and Huang for cancellative pairs, gives $(2.2499)^n$ for recovering pairs. We improve this to $(2.23949)^n$. The proof combines two entropy inequalities. One is derived directly from the recovering property, while the other applies the Fang-Huang bound to families obtained from the original pair by a construction of Mond, Souza and Versteegen. The two inequalities are then combined by a convex combination.
Read the full abstract

Information Theory

Multiple Access in Pinching-Antenna Systems: A Survey, Impairment Analysis, and Evaluation

Pinching-antenna systems attach dielectric pinches to a waveguide, creating line-of-sight radiation points within a few meters of any user. The pinches on one waveguide, however, radiate the same signal, unlike a conventional array, where each element transmits a dedicated signal. Separating the signals of multiple users therefore becomes challenging and requires a new perspective on multiple access. Most existing studies rest on an idealized model, and no survey examines the access schemes under realistic impairments. This article surveys multiple access in pinching-antenna systems and organizes fifty-six works into a unified taxonomy by spatial degrees of freedom. The users of one waveguide can be separated only in time, frequency, power, or guided mode, while multiple waveguides add the space domain. The article then identifies the impairments critical to this separation, which perturb the effective channel, leak interference across orthogonal resources, or couple the pinches on the uplink, and summarizes them in an impairment-versus-method map. A unified evaluation of time-, frequency-, power-, and space-domain access under identical channel and impairment models reveals that the degradation is method specific. The analytical and numerical results give insight into multiple access in these systems and provide a basis for its impairment-aware design, a necessary step toward their adoption in practical networks.
Read the full abstract