Information Theory Papers

ALT The simplification of complex dynamical systems is essential for efficient estimation and control. A principled approach to this task is through the lens of information-theoretic compression. The Past-Future Information Bottleneck (PF-IB) provides a theoretical framework for compressing linear dynamical systems. However, the standard formulation often lacks structural consistency, yielding representations that are not realizable as dynamical systems. By constraining the objective to a specific manifold of block Hankel matrices, which we prove is a Lie group, we bridge the gap between PF-IB and realization theory. Our approach ensures that the resulting compressed dynamics are realizable, thereby enabling its direct application to estimation and control. We demonstrate our approach in numerical simulations.

ALT We determine the maximum number of common zeros in projective space of any set of linearly independent homogeneous polynomials of the same degree, when the degree is smaller than the cardinality of the finite field. This proves the conjecture of Beelen, Datta and Ghorpade and determines the complete weight hierarchy of the corresponding projective Reed-Muller codes. The proof uses Green's hyperplane restriction bound, combined with a footprint argument that reduces the problem to the affine case solved by Heijnen and Pellikaan. Wei duality then determines the hierarchy in sufficiently large degrees, recovering the complete hierarchy in every degree for the projective plane. Finally, we prove an upper bound valid in every degree, and conjecture that it is always sharp.

ALT This paper investigates a non-orthogonal multiple access assisted coordinated beam hopping (NOMA-CBH) scheme in multidimensional very low Earth orbit (VLEO) satellite communication systems, where multiple satellites employ CBH and coordinated beams jointly serve ground users and a dedicated ground station (GS). To characterize the VLEO-specific propagation environment, we develop a channel model that incorporates atmospheric attenuation, Doppler effects, and pointing perturbations. Building upon this architecture and channel model, a low-complexity decoupled (LCD) algorithm is designed to optimize beam scheduling and power allocation. We further derive closed-form outage probability expressions for the ground users and the GS, perform asymptotic analysis to characterize their diversity orders, and evaluate the delay-limited throughput. Simulation results demonstrate that: i) The NOMA-CBH with LCD algorithm achieves an enhanced system sum rate relative to orthogonal multiple access with

ALT A collection of classical codes C₁,…,Cₘ has product expansion if every low-weight word in the sum of their extensions to the product space can be written as a sum of words supported on few lines, each line being a codeword of the corresponding Cᵢ. For m=2 product expansion is equivalent to robust testability of the tensor code, while for m≥ 3 it is strictly stronger; it is the hypothesis on the local codes behind recent constructions of good quantum LDPC codes, good quantum locally testable codes, and quantum codes with transversal non-Clifford gates. No explicit family over a fixed field was previously known to achieve constant rate, linear distance for both the code and its dual, and 3-fold product expansion at growing length. We prove that for the one-point evaluation codes Cᵢ of length Nᵢ=728⋅27ⁱ⁻¹ and pole order ⌊Nᵢ/5⌋ on the Garcia–Stichtenoth tower over F₇₂₉, the triple (Cᵢ,Cᵢ,Cᵢ) has product expansion with a constant independent of i. The dual codes Cᵢ⊥ then form an explicit fi

ALT Semantic communication (SemCom) using a relay node is considered, where the relay assists in conveying task-relevant information from a source to a destination, with meaning defined by classification labels. A joint end-to-end design of the source encoder, relay transformation, and destination decoders is developed to optimize both semantic inference accuracy and perceptual reconstruction quality for image data. Relay-assisted schemes are shown to outperform direct transmission, with gains that become more pronounced in low signal-to-noise ratio (SNR) regimes across different relaying strategies. Alongside these performance benefits, however, a key security vulnerability introduced by the relay is identified, and a Byzantine attack is formulated in which the relay injects structured, learned perturbations into its transmitted signal. The attack operates on intermediate communication representations subject to channel effects, with perturbations generated through a learned mapping appli

ALT Predictive interference management supports ultra-reliable low-latency communication (URLLC) by allocating finite-blocklength resources against a high conditional quantile of next-slot interference. Building on an extreme-value-theory/kernel-density-estimation (EVT/KDE) predictor with quantile-defined interference states, this paper makes the predictor resilient to unannounced shifts in the interference distribution. Its cumulative refitting on all past observations does not specify how the state partition and retained samples should evolve after a regime change. We show that drift first makes the quantile partition inefficient: cumulative refitting preserves tail support and coverage but cannot recover conditional resolution, and pays for it in channel use, whereas discarding history starves the tail estimator. We therefore propose event-triggered quantile-space adaptation. A nonparametric cumulative sum (CUSUM) on the predictor's level stream detects change. At each confirmed event,

ALT Partial information decomposition (PID) splits the information that two sources carry about a target into redundant, unique and synergistic parts, with nonnegative decompositions lying on a segment where redundancy measures are bounded by the positive part of the co-information and the smaller source-target information. We parameterize this segment by the overlap, the common excess of redundancy and synergy over their net balance, and show that for many of the named PID measures, their redundancy can be written as the largest positive part of the co-information over a set of reference distributions. This common form induces an ordering of those PIDs on the segment. With the smallest redundancy and synergy and the largest unique atoms of any nonnegative PID, the information-theoretic version of Hi-Fi, a feature-importance method, is the zero-overlap end of the segment for two sources, with the maximum overlap bound given by the minimum mutual information (MMI) PID. We introduce, by spli

ALT In goal-oriented communications, indirect source coding involves two sources: a semantic source X and an observation Z, which is the only source available at the encoder. In this paper, we consider this framework for classification, where the decoder only needs to reconstruct X. We argue that the gap between the indirect rate-distortion function and the performance of practical learned coding schemes, such as variational information bottleneck (VIB) and variational autoencoder (VAE) architectures, comes from three effects: the latent representation, the choice of the deep neural network (DNN) architecture and training loss, and whether the encoder is aware of the task. To quantify these effects, we introduce four operational rate-distortion functions that account for the DNN architecture and the training loss, and we establish a hierarchy among them. We then derive these functions for a Gaussian mixture source, where X is the mixture state. Numerical results, both for the Gaussian mixt

ALT Dephasing is a prominent source of decoherence in quantum communication, degrading phase coherence and transmission reliability. Therefore, knowledge of the physical channel parameters for reliable transmission is imperative, motivating the integration of quantum communication and sensing at the physical layer. Consequently, we study the transmission of coherent states over a von Mises dephasing channel affected by thermal noise. We consider a heterodyne receiver, for which, we first derive the symbol-error probability (SEP) and an accurate closed-form approximation, through which an irreducible asymptotic error floor due to the dephasing channel is identified. We note that the derived SEP is affected by the mismatch between the receiver's mean phase estimation and the true mean phase, thereby formalizing the interplay between sensing accuracy and communication reliability. In addition, we derive the Fisher information (FI) for the mean phase acquisition of the channel and provide clos

ALT Decisions about dense populations depend on how much will cross a boundary by a deadline and when the first member arrives. Conventional radar forms a range-Doppler map, whose cells add noise and whose detections merge unresolved members. We introduce over-the-scene computation, where illumination makes the scene compute such functionals without resolving members. With random echo phases, a correlator's mean output energy sums member reflectivities weighted by a kernel set by the waveform and template. The waveform's ambiguity function is this computation's transfer function, determining computable functionals and their noise cost. One readout aggregates members over a small delay-Doppler area but along a line segment growing with duration, longest for the chirp of matching slope among constant-envelope waveforms. Members predicted to share a range lie on such a line, so a chirp's mean beat spectrum is the predicted range profile at a look-ahead horizon set by its rate. For unbiased es

ALT Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is b-local if a collection of at most b codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of P is the code dimension at which the probability that an RLC in Fq^n satisfies P crosses 1/2 in a sharp transition. We show that the threshold of a b-local property P is within O(b) dimensions of the expectation threshold. This is the dimension predicted by the best union bound over covers of P: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix i

ALT For infinitely many rates R ∈ (0,1), we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate R with polynomially many codewords in a Hamming ball of relative radius bounded strictly below 1-R. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

ALT For classical-quantum multiple access channels (cq-MACs) with two senders, we give several general expressions for the capacity region, valid for arbitrary sequences of channels. In the case of asymptotically vanishing error (ε=0), the capacity region is expressed in terms of spectral inf-mutual information rates. For every 0≤ε<1, the ε-capacity region is expressed in terms of a quantity defined through a linear combination of three alternative hypotheses. In particular, the outer bound of Kubo and Nagaoka (2015) is tight. Our results include the quantum counterpart of the general formula of Han (1998) for the classical MAC. The most important ingredient is the one-shot inner bound of Sen (2021), which we apply to each member of an arbitrary channel sequence.

ALT Within the Thompson VLSI model, the first energy optimal decoding schemes (up to polylogarithmic factors) that also reach clock cycle lower bounds are constructed. Let N be block length. Then, there is an exponential error scaling function and a binary symmetric channel, such that for all f(N) that scales to zero more slowly than this, there is a decoding scheme for this channel with error probability that scales as O(f(N)) that has number of clock cycles T≤ O(√(-log(f(N)))polylog(N)) and energy E≤ O(N√(-log(f(N)))polylog(N)). This matches fundamental lower bounds up to polylogarithmic factors. The technique uses expander-graph based LDPC codes, a mesh network architecture, and a parallelization technique. The key technical result needed for this is a lemma in graph theory. This lemma is used to show that communication graphs of bounded node degree can be routed through two- and three-dimensional mesh networks without overflowing the memory of any mesh node. Upper bounds are also exten

ALT We consider private retrieval of the matrix product A⊤ B⁽ᶿ⁾ from replicated Pc-colluding servers when B⁽ℓ)=A+N⁽ℓ), with the innovations mutually independent and independent of the user-held A∈Fqᵐˣᵐ. The servers store the full library, correlated with A, which changes both the communication problem and the security definition: a secrecy condition including the stored library cannot hold, as the library itself partly reveals A. We therefore measure only additional leakage and require index privacy conditioned on A; both reduce to classical notions under independence. For A of rank k<m we prove, with no structural hypothesis on the map, D≥ H(A⊤ B⁽ᶿ⁾∣ A)/Cₚᵢᵣ(N,Pc,L)-o(km), where Cₚᵢᵣ(N,Pc,L) is the replicated Pc-colluding private-information-retrieval capacity. The proof rests on a colluding converse for servers storing arbitrary refinements of the demanded messages, whose answers need not be measurable functions of the functional-message library, and a privacy-transfer characterization.

ALT We consider lossless source coding with a marginal distribution constraint on the encoding symbols (SC-MDC). Unlike distribution matching, signal shaping and homophonic coding which require the symbols to be (approximately) i.i.d. following a target distribution, SC-MDC requires each symbol to have a marginal distribution that exactly matches the target distribution, which can be regarded as a perfect perceptual quality constraint on the symbols, and may have applications to wear leveling, source coding with cost and steganography. We give nonasymptotic lower and upper bounds on the optimal encoding length, and exactly characterize the coding rate (or the first-order term of the length) when the source distribution or the target distribution is uniform, or when the source is an i.i.d. sequence.

ALT We study the age of information and peak age of information in status update systems with an arbitrary number of independent sources sharing a single server with generally distributed service times. We consider a general age-dependent self-preemptive policy in which an in-service update from source c is preempted by a new same-source arrival with a probability pc(x) that depends on the elapsed service time x. This formulation subsumes the non-preemptive, fully self-preemptive, and probabilistically preemptive policies as special cases, and also accommodates threshold-based preemption. We develop a unified analytical framework based on non-homogeneous absorbing continuous-time Markov chains and semi-Markov chains to derive explicit expressions for the average age of information and peak age of information of each source under general per-source service-time distributions and age-dependent preemption rules. The framework applies to both single-source and multi-source systems and enables

ALT We propose a joint framework for constructing and decoding Logically Augmented (LA) quantum low-density parity-check (QLDPC) codes. This is motivated by the need for flexible coding rates and adaptive error protection while preserving block length and code structure. On the construction side, we use an auxiliary Logical Protection Code (LPC) to impose additional stabilizer constraints on selected logical qubits of a primary code. On the decoding side, the proposed decoder uses the LPC syndrome to generate logical error hypotheses and condition belief propagation (BP) on each hypothesis. The proposed Hierarchical Logical List Decoder (HLLD) is invoked only when the initial BP decoder for primary code fails to converge. It then selects the correction with the smallest Hamming weight among the syndrome-consistent candidates produced by hypothesis-conditioned BP runs. For numerical evaluation, we focus on short repetition LPCs, which provide a flexible means of trading rate for additional

ALT Many modern engineering applications require distributed problem-solving in which multiple nodes in a network cooperate to achieve a common optimization objective. Numerous distributed optimization and learning algorithms rely on consensus-based distributed coordination to ensure network-wide agreement via iterative local interactions. In these algorithms, the accuracy, frequency, and reliability of information exchange among network nodes directly influence system performance, including convergence behavior, training delay, and model accuracy. This tutorial article adopts a bottom-up approach to present the fundamentals of consensus averaging and distributed optimization methods, and highlights the impact of network connectivity, information flow, and communication uncertainty on network cooperation and optimization performance. Building on these theoretical insights, we discuss key design principles for communication-constrained distributed learning across diverse network topologies

ALT In this paper, we propose a threshold-triggered energy-accumulate-then-act backscatter communication system with retransmission under imperfect feedback detection. Under this system, harvested energy is accumulated across transmission blocks, and the backscatter device switches among different operation modes, including energy harvesting, initial transmission, and retransmission, according to its stored energy and decoded feedback. To characterize the resulting dynamics, the joint evolution of the packet-buffer and stored-energy states is modeled, based on which an embedded Markov chain is constructed to derive the steady-state energy distribution at the beginning of each update cycle. Subsequently, the average age of information (AAoI) is derived from the statistics of the inter-update interval and its correlation with the preceding packet system time, while the packet loss rate (PLR) caused by imperfect feedback detection is also obtained. Simulation results validate the analytical r