CS Paper Radar

Fast-Slow Communication with Endogenous Transport

Lav R. Varshney

cs.IT ·submitted 2026-09-13 17:27 UTC · v1
theoryunusual

Abstract

A communication system may convey urgent information through a fast physical stream and more specific information through a slower material stream. In several biological and engineered settings, however, the fast process also changes the transport law of the slow one. We study this architecture under a shared resource constraint, with a strictly increasing concave fast-channel capacity--cost function and a deadline-constrained slow molecular channel. We first characterize the capacity region under separated message routing and message-independent operating-point schedules, and identify the marginal criterion for complementarity rather than competition between the streams. For one-dimensional drift diffusion, we prove that arrival probability before a deadline is strictly log-concave in Péclet number. For a distinguishable-token deadline-erasure channel, any increasing concave transport-actuation law then yields an exact single-crossing theorem: complementarity exists if and only if an initial transport-assistance elasticity exceeds one, the transition is unique when it exists, and the decreasing allocation branch remains the Pareto boundary after convexification. For positive baseline drift and sufficiently strong coupling, a unique critical normalized deadline determines when complementarity disappears. Short- and long-deadline limits clarify the associated temporal regimes. Numerical examples for a finite-frame LTI-Poisson slow channel exhibit analogous allocation behavior with counting noise and intersymbol interference.

Closest papers

Nearest neighbours by meaning across the whole index.

Inverse Design of Finite-State Channels by Dynamic Measure Matching

cs.IT ·2026-11-02 ·Lav R. Varshney
similarity 0.54
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.

0.21

When Fresh Information Is Not Enough: Age-of-Actuation-Optimal Scheduling for Energy-Harvesting Actuators

cs.IT ·2026-10-15 ·Ali Nikkhah, Anthony Ephremides, Nikolaos Pappas
similarity 0.53
Abstract

We study transmission scheduling in an energy-harvesting actuation system where an actuation requires both a received update and available energy. While age of information (AoI) measures information freshness, age of actuation (AoA) measures the time elapsed since the latest completed actuation. The transmitter observes the receiver's AoA and battery state and decides whether to transmit a fresh update in each slot. We formulate average-AoA minimization as a Markov decision process and establish an AoA-threshold property for an optimal policy. We also derive the average AoA in closed form under the AoI-optimal policy, which is always-transmit. Numerical results show that AoA-aware scheduling can improve actuation freshness while reducing the number of transmissions, although information freshness may deteriorate. The two policies coincide for some pairs of channel success and energy-arrival probabilities. For a one-unit battery, the transmission rate under the AoA-optimal policy can vary nonmonotonically with the energy-arrival probability.

0.20

Local decisions, diffusive influence, and lower bounds for graphical balanced allocation

cs.DS math.PR ·2026-09-30 ·Obinna Okechukwu
theorycode/data similarity 0.53
Abstract · 28 pages, 2 figures. All numbered results are formalized in Lean 4: https://github.com/obinnaokechukwu/cycle-gap-lowerbound-lean

In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two endpoint loads, allowing edge-dependent thresholds and fresh randomization. Such a rule has an exact unit-discrepancy coupling: adding one ball to the initial state produces one tagged discrepancy at every later time. We represent the tag by conditional-expectation projections on the marked edge space and obtain diffusive displacement bounds. A transport-volume inequality then converts slow propagation of influence into lower bounds for the load gap. On the cycle with $n$ vertices, from every initial distribution and at every physical time $t\ge 1/n$, the expected gap is at least a constant times $\min\{\sqrt n,t^{1/4}\}$, and the gap exceeds this scale with probability at least $1/8$. After exactly $k\ge1$ allocations, the corresponding scale is $\min\{\sqrt n,(k/n)^{1/4}\}$. No stationarity, symmetry, recurrence, or moment assumption is used. A smoothed threshold rule in the same class has expected gap $O(\sqrt n\log n)$ up to any fixed polynomial time horizon, so the saturated cycle bound is sharp within the class up to a logarithmic factor. The general inequality also yields a lower bound of order $\sqrt{L/K}$ on the $L\times K$ rectangular torus $C_L\square C_K$; combined with a strategy-independent logarithmic bound, this gives order $\sqrt{L/K}+\log(LK)$. These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles. All numbered results are verified in Lean.

0.57

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.51
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

Contention Resolution with a Fast-but-Fickle Channel

cs.DC ·2026-11-09 ·Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young
theory similarity 0.51
Abstract

The contention-resolution problem studies how $n$ devices share a communication channel without centralized coordination. Classical models typically assume a single continuously available channel and focus on minimizing total completion time. However, modern wireless systems increasingly rely on shared spectrum, where access may be abruptly revoked by incumbent users. Motivated by this setting, we study contention resolution with two channels: a reliable slow channel and a faster channel that can be intermittently disabled by unpredictable eviction periods. Moving a batch of packets from the slow channel to the fast channel incurs a unit cost, while evictions from the fast channel impose a larger per-packet penalty. Our goal is to achieve asymptotically optimal latency while minimizing switching overhead relative to an optimal offline algorithm that knows the eviction schedule. We present Randomized Adaptive Channel Exploitation (RACE), a randomized algorithm that exploits the fast channel when available while maintaining progress on the slow channel during disruptions. When the fast channel has rate $ρ\in \bigl[Ω(\log n), O(\sqrt n)\bigr]$ and a sufficiently large constant-factor resource augmentation, RACE achieves an $O(1)$ competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is $O(ρ+\sqrt{n/m})$, where $m \geq 1$ is the number of fast-channel availability intervals used by OPT. We also prove a worst-case $Ω(\sqrt n)$ switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate $Ω(ρ)$ switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

0.31

Analysis of Triggered Packet Streams: Stochastic Bounds on System Time under General Triggering Delays

cs.PF math.PR ·2026-10-29 ·Mehran Rahnamania, Michel Mandjes, Farid Ashtiani
theory similarity 0.51
Abstract

Many emerging communication systems increasingly involve devices that transmit packets in multiple causally dependent stages as part of an internal workflow, rather than waiting for receiver feedback. To analyze such systems, we recently introduced the $\mathrm{M^T/G/1}$ queue, in which primary customers arrive according to an exogenous Poisson process, and each triggers a secondary customer to join the queue after an independent random delay, called the \textit{triggering delay}. Our prior heuristic approximations assume identical exponential service times, and our matrix-analytic framework assumes exponential triggering delays. However, no exact analysis is available when both distributions are general. In this paper, we derive stochastic bounds, in the usual stochastic order, on the system-time distribution of each customer class under general triggering-delay and service-time distributions. The service times within each primary--secondary pair may be generally dependent. Using sample-path coupling and level-crossing arguments, we show that the stationary workload is stochastically sandwiched between those of two classical queues: a two-class $\mathrm{M/G/1}$ queue with independent Poisson arrivals (lower bound), and a batch-arrival $\mathrm{M^{[2]}/G/1}$ queue where each primary--secondary pair arrives simultaneously (upper bound). Notably, these bounds do not depend on the triggering-delay distribution, and they are asymptotically tight in the sense that the stationary workload converges in distribution to that of the lower- and upper-bound queues as the triggering delays diverge to infinity and converge to zero in probability, respectively. We translate these workload bounds into system-time bounds for each customer class. Simulation experiments support these bounds.

0.08

Joint Freshness and Deadline Feasibility in Store-and-Forward Satellite IoT Networks

cs.NI ·2026-10-20 ·Suleyman Çıtır
similarity 0.50
Abstract

3GPP Release 19 supports store-and-forward satel- lite access, where traffic accumulated during feeder-link outages must be forwarded through finite, geometry-limited windows. Static priority levels offer little discrimination among large backlogs and ignore the decay in packet value. We formulate QoS feasibility for status updates, measured by destination freshness, and deadline-constrained event reports over periodic two-hop contacts with finite onboard storage. For general calendars, we derive ordering-sensitive miss, cohort-capacity, delivery-rate, and freshness bounds, including an exact status-only characterization. For single status flow and single event class sharing a contact pair per period, a finite-state program gives exact joint feasibility for arbitrary integer age thresholds. Numerical results quantify tradeoffs among load, capacity, deadline, and freshness tolerance.

0.34

Unbalanced W-Flow: Unbalanced Wasserstein Drifting under Finite-Batch Marginal Fluctuations

cs.LG cs.CV ·2026-10-13 ·Jongwook Jeon, Mingue Park, Jiwon Choi, Jaihoon Kim, Yunhong Min +1 more
similarity 0.50
Abstract · 31 pages, 9 figures, 9 tables

Teacher-free one-step generative models such as W-Flow learn directly from distributional objectives, with the Sinkhorn divergence providing the strongest empirical performance among the energies studied in W-Flow. However, Sinkhorn divergence is based on balanced optimal transport, whose exact marginal constraints can induce undesirable transport under finite minibatch fluctuations. We introduce UW-Flow, which replaces the balanced Sinkhorn energy with a debiased unbalanced Sinkhorn divergence and derives the corresponding Wasserstein velocity. The resulting dynamics retain W-Flow's cross-minus-self structure, recover the balanced limit, and preserve target identifiability under suitable assumptions. We further characterize the finite-batch velocity error of balanced and unbalanced transport by comparing each minibatch field with its population counterpart. Our analysis identifies conditions under which marginal relaxation yields smaller minibatch-to-population velocity error, and shows that for separated matched modes, balanced sensitivity grows with inter-mode separation while the corresponding Unbalanced Optimal Transport (UOT) sensitivity remains controlled by local transport geometry. Controlled experiments on fixed-support and continuous two-mode distributions support these predictions. On MNIST, CIFAR-10, and ImageNet-100, UW-Flow improves generation under matched training budgets, with the largest gains in unconditional generation and consistent improvements in the class-conditional setting.

0.16