Information Theory
Authentication over Arbitrarily Varying Channels with Causal Adversaries
Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey et al. (+1 more)
We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under
stochastic encoding, and not I-overwritable under deterministic encoding. In the
stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive
adversarial strategies. For
stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal
stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.
Read the full abstract ▾
All authors Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey, Oliver Kosut
Information Theory · Cross-listed from cs.LG
SemKV: Semantic Mixed-Precision KV Cache Quantization Guided by the Quality Cliff for Long-Context LLM Inference
Daeha Lee, Do-Hyung Kim and Jae-Hong Kim
The key-value (KV) cache is the dominant
memory bottleneck of long-context large
language model (LLM) inference, growing linearly with context length. We show that uniform KV quantization on a fractional-bit grid does not degrade gracefully: under a prespecified multi-seed statistical protocol, Llama-3.1-8B-Instruct with an affine quantizer is statistically indistinguishable from FP16 KV down to 2.322 code bits/value and collapses at 2.0 bits - a quality cliff in (2.0, 2.322] that reappears in generation-time quantization and multi-turn dialogue and transfers to Mistral-7B. The cliff reframes importance-aware mixed precision: above it, eight model-internal importance indicators are statistically interchangeable, so the benefit of mixing is grid interpolation, reaching average precisions uniform quantization cannot realize. SemKV preserves every
token, ranks
tokens by a model-internal score, and assigns two adjacent above-cliff precisions, achieving a measured 6.0x storage reduction with no statistically detectable quality difference from full KV (n=900, three seeds), and outperforming FP16
token pruning granted a 1.5x larger
memory budget. Replacing the affine base with a distortion-optimized quantizer (TurboQuant-MSE) lowers the cliff in every protocol tested, raising the no-detectable-loss operating point to 7.9x. The recipe: measure the cliff for the target deployment setting, then interpolate above it.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Rényi Entanglement of Purification Is Non-additive
Amir-Reza Negari and Zahra Baghali Khanian
Entanglement of purification is a fundamental measure of total correlations whose additivity remains unresolved. We study its additivity for classical states on two
qubits at different Rényi orders. For every $\alpha\in[0,1)$, we prove nonadditivity within this family, witnessed by two copies of a single state. We first solve the one-copy optimization exactly for the entire family at every Rényi order. We then restrict the two-copy optimization to a natural finite set of purifications and exhibit one whose
entropy is strictly below the product value. In contrast, for $\alpha\in[2,\infty]$ we prove additivity under tensor products within this family. The interval $\alpha\in[1,2)$, including the von Neumann case $\alpha=1$, remains open, and we
conjecture additivity there throughout the same family.
Read the full abstract ▾
Information Theory
A Complete Characterization of Tensorizable $f$-divergences
Rodrigo Cruz, Flavio P. Calmon and Qian Yu
Csiszar's formulation of the $f$-divergence introduced a vast family of functionals for quantifying dissimilarity between probability distributions. However, many applications in statistics and information theory rely only on a few $f$-divergences, such as the Kullback-Leibler divergence, the $\chi^2$-divergence, and the squared Hellinger distance. These divergences are especially useful because they admit simple compositional formulas under product measures, a property sometimes referred to as tensorization. In this work, we refine a formalism of tensorization previously introduced in the literature. Then, we show that any possible tensorization formula has a multi-affine form characterized by a single parameter, and identify all tensorizable $f$-divergences under our adopted notion of tensorization.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Classical Commitment over Quantum Channels with Limited Entanglement Assistance
Remi A. Chou
We study classical string commitment over
quantum channels with limited preshared
entanglement. For noninteractive protocols, we determine the commitment capacity of a class of channels with input dimension $d$ that, at each use, sample a pair of classical random variables $(F,Z)$, apply one of the $d^2$ Heisenberg–Weyl operators indexed by $Z$ to the input, and deliver the transformed
quantum system together with $F$ to the receiver. If $E$ is the available
entanglement rate in bits per channel use, then the capacity is $\min\{H(Z|F),\log_2d+E\}$. This class of channels encompasses
quantum erasure and depolarizing channels, as well as families of Pauli channels. Additionally, for interactive protocols, we show that the commitment rate cannot exceed $\log_2d+E$ bits per channel use, so that when $H(Z|F)\geq\log_2d+E$, interactive communication does not increase the capacity. As a consequence, for interactive protocols, we determine the capacity of the
quantum erasure channel.
Read the full abstract ▾
Information Theory
Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking
Sirin Chakraborty, Andrea Panebianco, Yuchen Tian et al. (+4 more)
This paper develops the first distributed cross-layer
algorithm for joint congestion control, routing, scheduling, and power control in covert multi-hop, multi-modal wireless networks, where
adversarial wardens (Willies) monitor
radio modalities via energy detection. The Detection Error Probability (DEP), the probability that a Willie fails to reliably detect ongoing transmissions, is generally non-concave in the transmit powers, making DEP-based covert network optimization challenging. We resolve this by constructing the tightest concave lower bound on the log-DEP, yielding a conservative convex problem that guarantees satisfaction of the original DEP constraints and unifies hard covertness constraints and covertness-utility maximization in a single problem. We develop a Parallel Proximal Alternating Direction Method of Multipliers (PP-ADMM)
algorithm for the resulting cross-layer problem and prove global Q-linear convergence, i.e., exponentially fast convergence, to the set of optimal solutions under standard regularity conditions. Numerical results confirm linear convergence and demonstrate robust tracking performance under channel fading and Willie mobility.
Read the full abstract ▾
All authors Sirin Chakraborty, Andrea Panebianco, Yuchen Tian, Kevin S Chan, Fikadu Dagefu, Yin Sun, Ness B. Shroff
Information Theory
Significance-Driven Semantic Communication
Christian McDowell, Andrea Panebianco, Sirin Chakraborty et al. (+1 more)
In this paper, we study a significance-driven cross- layer semantic communication design problem. Based on sta- tistical decision theory, we introduce an information-theoretic measure of per-sample data significance that quantifies the task-specific value of each individual observation. Using this metric, we formulate a cross-layer optimization problem that simultaneously optimizes (i) physical-layer semantic encoding and inference and (ii) MAC-layer resource allocation, with the objective of maximizing semantic spectrum efficiency, defined as the semantic value delivered per unit bandwidth per unit time. At the physical layer, we develop Meta-Learning Variational Information Bottleneck (Meta-VIB), a new semantic transceiver that employs a meta-learned hypernetwork to compress high- dimensional observations into semantically significant latents, enabling instantaneous adaptation to dynamic channel conditions and varying symbol budgets without online retraining. At the MAC layer, we model channel allocation as a Multi-Action Restless Multi-Armed Bandit (MA-RMAB) and adopt the Q- Maximization
algorithm, which dynamically allocates channel resources to sensors based on their semantic value of information. Experimental results on a real-world pedestrian safety
dataset demonstrate that our joint design achieves substantial gains in semantic spectrum efficiency over baselines, reaching up to 1000 times gain at an average SNR of 0 dB and 40 times gain at an average SNR of 5 dB.
Read the full abstract ▾
All authors Christian McDowell, Andrea Panebianco, Sirin Chakraborty, Yin Sun
Information Theory
Shortest self-orthogonal and LCD embeddings of linear codes over Fq+uFq
Junmin An and Jon-Lark Kim
This paper determines the exact lengths of shortest self-orthogonal and LCD
embeddings of linear codes over $\mathbb{F}_q+u\mathbb{F}_q$. By decomposing Gram
matrices over $\mathbb{F}_q+u\mathbb{F}_q$ into pairs of symmetric
matrices over the finite field $\mathbb{F}_q$, the
embedding problems are reduced to the congruence classification of symmetric and alternate
matrices over finite fields. Complete formulas for the shortest self-orthogonal
embedding length are obtained, with two distinct cases arising in both even and odd characteristic. We also show that every self-orthogonal code over $\mathbb{F}_q+u\mathbb{F}_q$ with nonzero free rank can be viewed as a shortest self-orthogonal
embedding of another code. We use Witt theory to construct all shortest self-orthogonal
embeddings. A complete characterization of shortest LCD
embeddings is also established in terms of invertible and arbitrary
matrices of prescribed sizes appended to a generator
matrix. Examples of self-orthogonal and LCD
embeddings with the largest minimum distance for the code considered are also presented, some of whose Gray images are optimal codes over $\mathbb{F}_q$.
Read the full abstract ▾
Information Theory · Cross-listed from stat.ML
Conformal Risk-Averse Decision Making with Optimized Certainty Equivalent Risk Control
Amirmohammad Farzaneh and Osvaldo Simeone
We study risk-averse decision making, in which an
agent selects actions while being uncertain about the true system state. The risk is measured via optimized certainty equivalent (OCE) metrics, which generalize popular criteria such as mean-variance risk and conditional value-at-risk (CVaR). We characterize the optimal policy under known distributions, and show that it reduces to a prediction set-based solution for the CVaR. This provides an operational interpretation of conformal prediction-type prediction sets. For unknown distributions, we develop a data-driven calibration strategy, based on a synthetic model for the likelihood and held-out calibration data, yielding high-probability control of the OCE risk. The approach is evaluated on two wireless beamforming settings.
Read the full abstract ▾
Information Theory
Fine Difference Structure and Prime-Power Depth of Bent Partitions
Zhaorui Wu
A $p$-ary bent partition of $\mathbb{F}_p^n$ is a partition into $K$ nonempty
cells such that every balanced assignment of its
cells to $\mathbb{F}_p$ produces a bent function. It was asked whether every possible depth $K$ is a power of $p$; for general $p$, previous affirmative results required regularity or
cell-
symmetry hypotheses. We prove the stronger unconditional statement that, for every nonzero $h$, exactly $p^n/K$ points remain in the same fine
cell under translation by $h$. Thus the fine
cells form a partitioned difference family and the fine label map is zero-difference balanced. Consequently $K\mid p^n$, so $K=p^t$; nonempty
cells further give $1\le t<n$. In even dimension, the classical
cell-size
theorem yields $K\mid p^{n/2}$. Together with the known odd-dimensional ternary three-fibre parameter restriction, this gives the global bound $t\le\lfloor n/2\rfloor$. The proof is an exact finite average over balanced coarsenings. The main counting identity and selected consequences are formalized and kernel-checked in Lean 4.
Read the full abstract ▾
Information Theory
Ada-TokenCom: Rate-Adaptive Token Communications via Large-Model-Driven Token Compression and Generation
Zijun Zhang, Li Qiao, Mahdi Boloursaz Mashhadi et al. (+3 more)
Token Communications (TokenCom) has recently emerged as a new paradigm in which
tokens serve as unified units for communication and computation, enabling efficient
multimodal semantic and goal-oriented transmission. In this paper, we develop Ada-TokenCom, a rate-adaptive TokenCom framework based on large autoregressive models, which integrates next-
token prediction with arithmetic coding to achieve ultra-low bitrate semantic communication at the
token level. We propose a mixed reconstruction/generation scheme, where the transmitter encodes and transmits the highly informative
tokens at the beginning of the
token sequence leveraging a pre-trained autoregressive large model, while the receiver uses an identical model to predict the rest. Moreover, we design a Lyapunov-based
algorithm to dynamically optimize both the source compression rate and the modulation and coding scheme, adapting to time-varying network conditions. Simulation results demonstrate that our proposed Ada-TokenCom framework outperforms both digital and deep joint source-channel coding-based semantic communication baselines.
Read the full abstract ▾
All authors Zijun Zhang, Li Qiao, Mahdi Boloursaz Mashhadi, Zhen Gao, Mehdi Bennis, Kaibin Huang
Information Theory
ODMA-based MIMO Massive Unsourced Random Access with Soft-Output Polar Codes
Tianya Li, Xiaoran Zhang, Nan Hu et al. (+4 more)
This paper investigates the design of the on-off division multiple access (ODMA) transmission scheme for multiple-input multiple-output (
MIMO) massive unsourced random access (URA) systems with soft-output (SO) polar codes. First, a three-segment pilot-uncoupled coding scheme is introduced under the ODMA framework, which reduces the coding rate of the data segment without increasing the transmission overhead, improving the overall system performance. Building upon this architecture, a hierarchical pattern detection framework is developed. Specifically, a coarse-grained candidate set of transmission patterns is first identified through correlation operations. Based on this, a message-passing (MP)-based pattern detection
algorithm is developed to iteratively estimate the posterior probabilities of transmission patterns, followed by the maximum a posteriori (MAP) estimation to obtain the precise pattern detection result. Furthermore, a joint pattern detection and data decoding
algorithm based on the bit-wise SO information of polar decoder is investigated, where the posterior probability information provided by the polar decoder is exploited to refine the pattern detection and contribute to an improved accuracy. In addition, by leveraging bit-wise SO information of the successive cancellation list polar decoder, an MP-based iterative decoding
algorithm is developed to significantly enhance the decoding performance. The proposed scheme simultaneously exploits the transmission gain of uncoupled-ODMA framework, the coding gain of polar codes in the short-blocklength regime, and the iterative decoding gain enabled by SO information, while the computational complexity is significantly reduced through the hierarchical detection framework. Simulation results demonstrate that the proposed scheme achieves strong robustness ...
Read the full abstract ▾
All authors Tianya Li, Xiaoran Zhang, Nan Hu, Yongpeng Wu, Wenjun Zhang, Xiang-Gen Xia, Chengshan Xiao
Information Theory
Finite Sample Bounds for Composite Hypothesis Testing
Elías Vera-Sigüenza and Amedeo Roberto Esposito
We investigate composite binary hypothesis testing in the finite sample regime under asymmetric error constraints. Using Rényi divergences, we derive explicit achievability and converse bounds for the optimal Type II error. When the Type I error is constrained to decay exponentially with sample size, the bounds identify a phase transition and yield a strong converse above it. In the composite problem, the phase transition threshold is given by the joint KL projection over the alternative and null classes. Achievability is obtained through a joint Rényi projection whose log likelihood ratio defines a single test with uniform error control over both hypothesis classes, without requiring the projected pair to be least favourable. For compact convex classes with full support on a finite alphabet, we determine the exact error exponents on both sides of the transition and show that the achievable exponent is attained at a unique Rényi order. The same framework recovers the fixed Type I composite Chernoff–Stein exponent and yields a
polynomial refinement of the finite sample achievability result. We further identify conditions under which the projected pair is least favourable at finite sample size.
Read the full abstract ▾
Information Theory · Cross-listed from cs.AI
Should I Use This Synthetic Dataset for Training? How to Test with Minimal Real Data
Zhenyu Tao, Wei Xu, Xiaohu You et al. (+2 more)
Digital twins (DTs) and learned world models are increasingly used to generate synthetic data that augment the scarce real
datasets available for training artificial intelligence (AI) models in engineering systems. Owing to the inevitable simulation-to-reality (sim-to-real) gap, however, augmentation may fail to improve the performance of the trained model on the real data distribution. This paper addresses the resulting decision problem: Given a real
dataset, a candidate synthetic
dataset, and a fixed learning
algorithm, decide whether training on the augmented
dataset improves the true, population-level performance, while consuming as few real test data points as possible. Two formulations are considered: a direct test on the mean loss difference between the two trained models, and a
symmetry-based test on the paired loss difference, which trades a stronger null assumption for faster evidence accumulation. For the latter, we introduce the {adaptive e-process sign-flip test} (aeSFT), a doubly adaptive procedure that adapts both the number of Monte Carlo sign-flip rounds, and hence the computational cost, and the amount of real test data consumed. aeSFT yields anytime-valid Type-I error control, with no need to pre-specify the test-set size. Experiments on a synthetic-data classification task, a DT-aided wireless packet-scheduling task, and a
radio-map prediction task show that aeSFT identifies useful synthetic data using substantially fewer real test samples than mean-based sequential testing, matches the power of fixed-sample sign-flip testing and the paired $t$-test, while keeping the false-positive rate below the target level.
Read the full abstract ▾
All authors Zhenyu Tao, Wei Xu, Xiaohu You, Petar Popovski, Osvaldo Simeone
Information Theory · Cross-listed from physics.comp-ph
Accelerated S-NFC for Million-Chaff RCS Computation Using Low-Rank Compression of Concatenated Block Rows
Dong-Yeop Na, Somyeong Lee and Chung Hyun Lee
Sparsification via neglecting far-field coupling (S-NFC) enables fast full-wave radar-cross-section analysis of large-scale chaff clouds by retaining only significant local electromagnetic interactions. This letter further accelerates S-NFC by concatenating the retained off-diagonal interaction blocks associated with each receiving chaff element and applying a joint low-rank factorization with a shared receiving-side basis. Exact self interactions are preserved, while repeated chaff templates reuse precomputed lower–upper factorizations of the self-interaction blocks. The compressed formulation reduces retained-coupling storage and
matrix–vector multiplication cost and also decreases the number of iterations required by the generalized conjugate residual solver. Numerical tests with 100,000 chaff elements demonstrate sub-$1\%$ complex-far-field error for low-rank approximations in sparse regimes and identify a practical self-only limit at sufficiently large mean spacing. For a one-million-chaff plume, the proposed compressed S-NFC achieves a $6.92\times$ end-to-end speedup over uncompressed S-NFC while storing only $6.60\%$ of the retained coupling, with a complex-far-field error of $0.253\%$.
Read the full abstract ▾
Information Theory
Low-Altitude Fluid Antenna Network with Multi-Agent Reinforcement Learning
Tong Zhang, Yanfei Su, Shuai Wang et al. (+3 more)
Low-altitude wireless networks (LAWNs) integrate terrestrial and aerial platforms to provide ubiquitous communication, sensing, and localization services for unmanned aerial vehicles (
UAVs) and electric vertical takeoff and landing (eVTOL) aircraft. However, dynamic air-ground and air-air channels, abrupt blockages, and heterogeneous interference hinder the realization of this goal. Nevertheless, fluid
antenna (FA), a cutting-edge multiple-input multiple-output (
MIMO) technique, overcomes these challenges by reconfiguring
antenna positions to unlock additional spatial degrees-of-freedom. In this paper, towards bringing low-altitude FA networks into reality, we study the fast and high-performance FA reconfiguration for low-altitude FA networks with multi-
agent reinforcement learning (MARL). Specifically, we present an electromagnetic digital twin (EM-DT)-assisted MARL framework. To fill the sim-to-real gap, we introduce a two-stage transfer learning framework. Our case study shows that joint FA positions and beamforming optimization can enhance the system sum-rate by 118.5%, compared to the fixed position baseline. This gain comes from the dynamic millisecond timescale reconfiguration of FA arrays and the adaptive steering of beams toward aerial users with mobility.
Read the full abstract ▾
All authors Tong Zhang, Yanfei Su, Shuai Wang, Wanli Ni, Chengzhong Xu, Huseyin Arslan
Information Theory · Cross-listed from cs.CC
Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
Sidhant Saraogi
Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new
polynomial method argument that controls collisions in sumsets of matching vectors.
Read the full abstract ▾
Information Theory · Cross-listed from math-ph
Difference equations of average entropies
Youyi Huang, Linfeng Wei, Lu Wei et al. (+1 more)
Exact cumulants of
entanglement entropies of random state ensembles have traditionally been studied within the random
matrix framework. In this work, we propose an alternative approach based on the intrinsic connection to integrable systems. The central idea is to embed entropic quantities into tau functions satisfying Toda-type
lattice equations, which in turn yield linear difference equations for their averages. Directly solving the difference equations recovers exact
entropy formulas in the literature. The integrable systems approach bypasses the case-by-case, ensemble-dependent derivations required by random
matrix methods. The approach also suggests a possible route towards unified and more efficient higher-order cumulant calculations by exploring integrable hierarchies.
Read the full abstract ▾
All authors Youyi Huang, Linfeng Wei, Lu Wei, Peter J. Forrester