In applications of remote sensing, estimation, and control, timely communication is critical but not always ensured by high-rate communication. This work proposes decentralized age-efficient transmission policies for random access channels with $M$ transmitters. We propose the notion of age-gain of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a decentralized manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large $M$ , we prove that when the arrival rate is small (below $\frac {1}{eM}$ ), slotted ALOHA-type algorithms are order optimal. As the arrival rate increases beyond $\frac {1}{eM}$ , while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates $\theta $ , $\theta =\frac {1}{o(M)}$ , the proposed algorithms provide a multiplicative gain of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI. We further extend our results to other random access technologies such as Carrier-sense multiple access (CSMA).

An erasure broadcast network is considered with two disjoint sets of receivers: a set of weak receivers with allequal erasure probabilities and equal cache sizes, and a set of strong receivers with all-equal erasure probabilities and no cache memories. Lower and upper bounds are presented on the capacity-memory tradeoff of this network (the largest rate at which messages can be reliably communicated for given cache sizes). The lower bound is achieved by means of a joint cachechannel coding scheme and significantly improves over traditional schemes based on separate cache-channel coding. In particular, it is shown that joint cache-channel coding offers new global caching gains that scale with the number of strong receivers in the network. The upper bound uses bounding techniques from degraded broadcast channels and introduces an averaging argument to capture the fact that the contents of the cache memories are designed before knowing users’ demands. The derived upper bound is valid for all stochastically degraded broadcast channels. The lower and upper bounds match for a single weak receiver (and any number of strong receivers) when the cache size does not exceed a certain threshold. Improved bounds are presented for the special case of a single weak and a single strong receiver with two files and the bounds are shown to match over a large range of cache sizes.

A fundamental question in designing lossy data compression schemes is how well one can do in comparison with the rate-distortion function, which describes the known theoretical limits of lossy compression. Motivated by the empirical success of deep neural network (DNN) compressors on large, realworld data, we investigate methods to estimate the rate-distortion function on such data, which would allow comparison of DNN compressors with optimality. While one could use the empirical distribution of the data and apply the Blahut-Arimoto algorithm, this approach presents several computational challenges and inaccuracies when the datasets are large and high-dimensional, such as the case of modern image datasets. Instead, we reformulate the rate-distortion objective, and solve the resulting functional optimization problem using neural networks.We apply the resulting rate-distortion estimator, called NERD, on popular image datasets, and provide evidence that NERD can accurately estimate the rate-distortion function. Using our estimate, we show that the rate-distortion achievable by DNN compressors are within several bits of the rate-distortion function for realworld datasets. Additionally, NERD provides access to the ratedistortion achieving channel, as well as samples from its output marginal. Therefore, using recent results in reverse channel coding, we describe how NERD can be used to construct an operational one-shot lossy compression scheme with guarantees on the achievable rate and distortion. Experimental results demonstrate competitive performance with DNN compressors.

Degraded K-user broadcast channels (BC) are studied when receivers are facilitated with cache memories. Lower and upper bounds are derived on the capacity-memory tradeoff, i.e., on the largest rate of reliable communication over the BC as a function of the receivers’ cache sizes, and the bounds are shown to match for interesting special cases. The lower bounds are achieved by two new coding schemes that benefit from nonuniform cache assignments. Lower and upper bounds are also established on the global capacity-memory tradeoff, i.e., on the largest capacity-memory tradeoff that can be attained by optimizing the receivers’ cache sizes subject to a total cache memory budget. The bounds coincide when the total cache memory budget is sufficiently small or sufficiently large, where the thresholds depend on the BC statistics. For small cache memories, it is optimal to assign all the cache memory to the weakest receiver. In this regime, the global capacity-memory tradeoff grows by the total cache memory budget divided by the number of files in the system. In other words, a perfect global caching gain is achievable in this regime and the performance corresponds to a system where all the cache contents in the network are available to all receivers. For large cache memories, it is optimal to assign a positive cache memory to every receiver such that the weaker receivers are assigned larger cache memories compared to the stronger receivers. In this regime, the growth rate of the global capacity-memory tradeoff is further divided by the number of users, which corresponds to a local caching gain. It is observed numerically that a uniform assignment of the total cache memory is suboptimal in all regimes unless the BC is completely symmetric. For erasure BCs, this claim is proved analytically in the regime of small cache-sizes.

Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario.

In this paper, we consider a lossy single-user caching problem with correlated sources. We first describe the fundamental interplay between the source correlations, the capacity of the user's cache, the user's reconstruction distortion requirements, and the final delivery-phase (compression) rate. We then illustrate this interplay using a multivariate Gaussian source example and a binary symmetric source example. To fully explore the effect of the user's distortion requirements, we formulate the caching problem using f-separable distortion functions recently introduce by Shkel and Verdú. The class of f-separable distortion functions includes separable distortion functions as a special case, and our analysis covers both the expected- and excess-distortion settings in detail. We also determine what “common information” should be placed in the cache, and what information should be transmitted during the delivery phase. To this end, two new common-information measures are introduced for caching, and their relationship to the common-information measures of Wyner, Gács, and Körner is discussed in detail.