CS Paper Radar

Inverse Design of Finite-State Channels by Dynamic Measure Matching

Lav R. Varshney

cs.IT ·submitted 2026-11-02 02:20 UTC · v1

Abstract

Inspired by the optimization approach to biology, we formulate an inverse problem for communication with memory: construct a finite-state channel for which a given signaling behavior supports capacity-achieving codes. Dynamic measure matching is introduced to turn a directed-information converse into conditions on the channel dynamics. These conditions lead to a new notion of dynamic surprise: the log ratio of physical to test output probabilities with a continuation correction for future signaling opportunities. The matching inequalities bound its conditional mean. For fixed architecture, test law, and potential, channel row synthesis under convex physical restrictions is convex. For every signaling constraint represented by a finite irreducible constrained graph of positive entropy, we construct a channel law under which undesired inputs remain available and behaviorally distinct while incurring a strict information penalty. A noisy refractory family has an exact capacity plateau, followed by an interval in which Shannon and zero-error feedback capacities differ. Explicit zero-error codes attain capacity in the graph construction and on the plateau. In this family, a Gibbs choice maximizes the penalty and makes dynamic surprise equal its conditional mean on every transition, yielding an exact trajectory-wise likelihood identity, a finite-block bound on successful decoding with premature requests, and an exponential strong converse. An exact gap decomposition into action residuals and output-law divergence constrains every reliable capacity-approaching code. Within the strict plateau, positive discrimination exponents for unused dynamics require a positive rate loss, while sparse probing permits consistent estimation at asymptotic capacity. A chemical channel illustrates how premature stimulation can alter future responsiveness while leaving the immediate output law unchanged.

Closest papers

Nearest neighbours by meaning across the whole index.

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

cs.IT quant-ph ·2026-09-28 ·Tina Shariat, Matt Hoogsteder-Riera, Marco Tomamichel
similarity 0.65
Abstract · 25 pages, 1 figure

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

0.35

Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs

cs.IT cs.AI ·2026-10-11 ·Gongpu Chen, Deniz Gündüz
similarity 0.60
Abstract · 18 pages, 6 figures

This paper investigates a new role of randomness in stochastic policies--as a medium for embedding and communicating information. Specifically, we consider an agent interacting with an environment according to a prescribed stochastic policy. By carefully modulating the random action realizations of the policy, information can be embedded into the agent's behavior without altering the prescribed action distribution. We cast this problem as a channel coding problem, in which the controlled system implicitly serves as a communication channel. We then propose a coding scheme, termed posterior-matching randomness modulation (PRAM), that selects actions according to the message to be transmitted. With the aid of common randomness independent of the control system, PRAM preserves the prescribed action distribution for every state and every message. We further prove that PRAM is asymptotically reliable: the message can be decoded with arbitrarily small error probability as the observed state trajectory becomes sufficiently long. Experiments demonstrate the effectiveness of the proposed framework in applications including multi-bit policy watermarking and trajectory provenance.

0.28

Efficiently computable bounds on the energy-constrained quantum reading capacity

cs.IT quant-ph ·2026-10-06 ·Vishal Singh, Zixin Huang, Mark M. Wilde
similarity 0.60
Abstract · 22+5 pages, 2 figures

In quantum reading, classical messages are encoded in sequences of quantum channels and recovered by probing the channels and processing their outputs. We study the reading capacity of a finite family of finite-dimensional channels under an average constraint on the probing energy, allowing arbitrary adaptive operations between channel uses. Using an input-dependent chain rule for the Belavkin-Staszewski relative entropy, we derive a converse bound expressed as an optimization involving channel Choi operators and the operator relative entropy. This formulation admits semidefinite approximations and reduces, without an energy constraint, to a channel information radius. To obtain achievable rates, we construct bilinear semidefinite lower approximations to a standard non-adaptive reading bound. Alternating optimization produces feasible probe states and encoding distributions, whose Holevo information gives a directly evaluable achievable rate. For jointly classical-quantum channels, we derive a separate converse based on the Umegaki relative entropy. Without an energy constraint, this converse matches a non-adaptive achievable rate, recovering a recent result of Pascual Abraldes and Winter: non-adaptive protocols suffice to achieve the unconstrained reading capacity of jointly classical-quantum channels.

0.16

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.59
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22

No information transmission through quantum channels above capacity

cs.IT quant-phmath-ph ·2026-09-08 ·Hao-Chung Cheng, Marco Tomamichel
theoryhighly cited similarity 0.56
Abstract

We show that the capacity of a quantum channel demarcates a phase transition: while reliable transmission below capacity is always possible, any attempt to transmit information above it fails catastrophically. Specifically, we prove exponential strong converse theorems for unassisted quantum and classical communication over arbitrary finite-dimensional memoryless quantum channels. At rates beyond the respective capacity, the entanglement-generation fidelity and the success probability for classical communication decay exponentially with the number of channel uses. This rules out transmission above capacity even when one tolerates arbitrarily large errors. Our proof follows the classical Arimoto strategy, augmented by a crucial new ingredient: integral representations of Rényi information measures that lead to asymptotic continuity bounds for Rényi capacities.

0.48

Thermodynamic characterization of message-passing: Framework and initial study

cs.IT cond-mat.stat-mech ·2026-10-26 ·Kalana G. Abeywardena, Stark C. Draper
publishedtheory similarity 0.56
Abstract · Published in IEEE Journal on Selected Areas in Information Theory (JSAIT), August 2026. 36 pages, 10 figures

We study the thermodynamic efficiency of message-passing decoders using the mismatch cost framework. This framework quantifies the excess entropy generated when a system operates away from the thermodynamically optimal initial distribution. It provides a computable lower bound on irrecoverable energy loss. The decoder is modeled as a main decoding program with local message updates implemented as subroutines. Memory is treated as an external copying subsystem whose thermodynamic cost is excluded. Studying the $[7,4]$ Hamming code transmitted over a binary erasure channel, we show how the channel-induced initialization statistics and the step-wise evolution of the algorithmic state distribution during decoding determine the total mismatch cost. We further show that different thermodynamically optimal state distributions, representing different underlying physical implementations of the decoder, can produce different thermodynamic costs for identical decoding dynamics. Conditioning the input distribution on correctable and non-correctable erasure patterns further reveals distinct thermodynamic signatures. These results demonstrate that thermodynamic cost is jointly governed by decoding dynamics, input statistics, and hardware characteristics. This points to opportunities for thermodynamically-informed decoder design to realize energy-efficient physical implementations.

0.59

Causal Information Exchange as a Necessary Condition for Adaptive Regulation: A Perturbational Framework for Life and Agency

cs.IT ·2026-10-16 ·Brian LuValle, Abicumaran Uthamacumaran, Hector Zenil
theory similarity 0.56
Abstract · 59 pages, 30 figures including supplemental sections

Information exchange can support living organisation without providing a sufficient criterion for life. We develop a perturbational framework that distinguishes causal transmission, directional imbalance, internal retention, response structure and functional regulation. Randomised interventions define Shannon information channels; for deterministic binary recipients, their context-conditioned mutual information is exactly a paired perturbation-response indicator. Spatial and temporal averages of these local channels measure information-exposure density, rather than joint information or conserved information flux. Complementary Coding Theorem Method and Block Decomposition Method (BDM) estimates describe response and trajectory structure. A same-shaped zero-mask reference separates raw BDM from a structural contrast; neither is a channel mutual information. Retained exploratory BDM plots are distinguished from the normalised causal-channel results. Retention-weighted coupling and directionality obey algebraic bounds, and ensemble reciprocity need not imply reciprocity within individual contexts. For a specified binary sensor--internal-channel--actuator task, we derive a positive information lower bound from successful regulation and construct controllers with identical information profiles but opposite functional outcomes. A study of 2,000 ordered elementary-cellular-automaton rule pairs, six detailed examples, recurrence and lossless coding analyses, and a signed-network extension demonstrates dissociations among perturbational responsiveness, structural regularity and recurrence. The results establish causal information as a necessary resource for the stated form of adaptive regulation, while showing why neither causal coupling nor response complexity alone measures agency or life.

0.30

When Information Is Not Enough: Accuracy-Constrained Thermodynamic Costs of Binary Classification

cs.IT ·2026-09-25 ·Xuening Wu
theory similarity 0.55
Abstract

How much entropy must a physical classifier produce to achieve a prescribed accuracy? Rate--distortion theory specifies the minimum information required, but does that information threshold suffice to determine the physical cost? We show that it does not, even for a binary task and a two-state memory. For a uniform binary target observed through a finite symmetric experiment, replacing the classification-error constraint with its necessary mutual-information threshold strictly lowers the infimum of entropy production under a common operation time, integrated mobility budget, and sufficiently large finite transition-rate cap. The separation holds whenever the target error lies strictly between the Bayes error of the observations and chance. Two results establish this physical gap. First, ordering observations by posterior confidence gives exact transport--risk and transport--information frontiers. Observations with the same Bayes error can have different cost frontiers. Second, we construct bounded-rate protocols that realize prescribed encoders with write probabilities below one, starting from exact reset, with an explicit excess cost above the transport bound. An achievable information-constrained cost then falls below a lower bound valid for every task-feasible protocol. Examples with repeated noisy observations illustrate the separation. The results identify a limitation of information-only benchmarks for physical classification: task accuracy and kinetic constraints must be retained explicitly. The cost analyzed is total entropy production during memory writing, excluding data acquisition, controller operation, and subsequent reset.

0.35