Search

The work here studies the communication cost for a multi-server multi-task distributed computation framework, and does so for a broad class of functions and data statistics. Considering the framework where a user seeks the computation of multiple complex (conceivably non-linear) tasks from a set of distributed servers, we establish communication cost upper bounds for a variety of data statistics, function classes and data placements across the servers. To do so, we proceed to apply, for the first time here, K\"orner's characteristic graph approach -- which is known to capture the structural properties of data and functions -- to the promising framework of multi-server multi-task distributed computing. Going beyond the general expressions, and in order to offer clearer insight, we also consider the well-known scenario of cyclic dataset placement and linearly separable functions over the binary field, in which case our approach exhibits considerable gains over the state of art. Similar gains are identified for the case of multi-linear functions., Comment: Submitted to Entropy

The work considers the $N$-server distributed computing scenario with $K$ users requesting functions that are linearly-decomposable over an arbitrary basis of $L$ real (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion) $\epsilon$, reduced computing cost ($\gamma$; the fraction of subfunctions each server must compute), and reduced communication cost ($\delta$; the fraction of users each server must connect to). For any given set of $K$ requested functions -- which is here represented by a coefficient matrix $\mathbf {F} \in \mathbb{R}^{K \times L}$ -- our problem is made equivalent to the open problem of sparse matrix factorization that seeks -- for a given parameter $T$, representing the number of shots for each server -- to minimize the reconstruction distortion $\frac{1}{KL}\|\mathbf {F} - \mathbf{D}\mathbf{E}\|^2_{F}$ overall $\delta$-sparse and $\gamma$-sparse matrices $\mathbf{D}\in \mathbb{R}^{K \times NT}$ and $\mathbf{E} \in \mathbb{R}^{NT \times L}$. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our $\mathbf{D},\mathbf{E}$ by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split $\mathbf{F}$ into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of $\mathbf{D}$ and $\mathbf{E}$., Comment: 65 Pages, 16 figure. The manuscript is submitted to IEEE Transactions on Information Theory

In this paper, we investigate the problem of multi-user linearly decomposable function computation, where $N$ servers help compute functions for $K$ users, and where each such function can be expressed as a linear combination of $L$ basis subfunctions. The process begins with each server computing some of the subfunctions, then broadcasting a linear combination of its computed outputs to a selected group of users, and finally having each user linearly combine its received data to recover its function. As it has become recently known, this problem can be translated into a matrix decomposition problem $\mathbf{F}=\mathbf{D}\mathbf{E}$, where $\mathbf{F} \in \mathbf{GF}(q)^{K \times L}$ describes the coefficients that define the users' demands, where $\mathbf{E} \in \mathbf{GF}(q)^{N \times L}$ describes which subfunction each server computes and how it combines the computed outputs, and where $\mathbf{D} \in \mathbf{GF}(q)^{K \times N}$ describes which servers each user receives data from and how it combines this data. Our interest here is in reducing the total number of subfunction computations across the servers (cumulative computational cost), as well as the worst-case load which can be a measure of computational delay. Our contribution consists of novel bounds on the two computing costs, where these bounds are linked here to the covering and packing radius of classical codes. One of our findings is that in certain cases, our distributed computing problem -- and by extension our matrix decomposition problem -- is treated optimally when $\mathbf{F}$ is decomposed into a parity check matrix $\mathbf{D}$ of a perfect code, and a matrix $\mathbf{E}$ which has as columns the coset leaders of this same code., Comment: This paper is submitted to the IEEE International Symposium on Information Theory (ISIT) 2024

This paper answers a fundamental question about the exact distribution of the signal-to-interference-plus-noise ratio (SINR) under matched-filter (MF) precoding. Specifically, we derive the exact expressions for the cumulative distribution function (CDF) and the probability density function (PDF) of SINR under MF precoding over Rayleigh fading channels. Based on the exact analysis, we then rigorously prove that the SINR converges to some specific distributions separately in high SNR and in massive MIMO. To simplify the exact result in general cases, we develop a good approximation by modelling the interference as a Beta distribution. We then shift to the exact analysis of the transmit rate, and answer the fundamental question: How does the exact rate converge to the well-known asymptotic rate in massive MIMO? After that, we propose a novel approximation for the ergodic rate, which performs better than various existing approximations. Finally, we present some numerical results to demonstrate the accuracy of the derived analytical models., Comment: 6 pages, 3 figures

This paper studies a multiaccess coded caching (MACC) where the connectivity topology between the users and the caches can be described by a class of combinatorial designs. Our model includes as special cases several MACC topologies considered in previous works. The considered MACC network includes a server containing $N$ files, $\Gamma$ cache nodes and $K$ cacheless users, where each user can access $L$ cache nodes. The server is connected to the users via an error-free shared link, while the users can retrieve the cache content of the connected cache-nodes while the users can directly access the content in their connected cache-nodes. Our goal is to minimise the worst-case transmission load on the shared link in the delivery phase. The main limitation of the existing MACC works is that only some specific access topologies are considered, and thus the number of users $K$ should be either linear or exponential to $\Gamma$. We overcome this limitation by formulating a new access topology derived from two classical combinatorial structures, referred to as the $t$-design and the $t$-group divisible design. In these topologies, $K$ scales linearly, polynomially, or even exponentially with $\Gamma$. By leveraging the properties of the considered combinatorial structures, we propose two classes of coded caching schemes for a flexible number of users, where the number of users can scale linearly, polynomially or exponentially with the number of cache nodes. In addition, our schemes can unify most schemes for the shared link network and unify many schemes for the multi-access network except for the cyclic wrap-around topology., Comment: 48 pages

This work studies a well-known shared-cache coded caching scenario where each cache can serve an arbitrary number of users, analyzing the case where there is some knowledge about such number of users (i.e., the topology) during the content placement phase. Under the assumption of regular placement and a cumulative cache size that can be optimized across the different caches, we derive the fundamental limits of performance by introducing a novel cache-size optimization and placement scheme and a novel information-theoretic converse. The converse employs new index coding techniques to bypass traditional uniformity requirements, thus finely capturing the heterogeneity of the problem, and it provides a new approach to handle asymmetric settings. The new fundamental limits reveal that heterogeneous topologies can in fact outperform their homogeneous counterparts where each cache is associated to an equal number of users. These results are extended to capture the scenario of topological uncertainty where the perceived/estimated topology does not match the true network topology. This scenario is further elevated to the stochastic setting where the user-to-cache association is random and unknown, and it is shown that the proposed scheme is robust to such noisy or inexact knowledge on the topology., Comment: 39 pages

The multi-user linearly-separable distributed computing problem is considered here, in which $N$ servers help to compute the real-valued functions requested by $K$ users, where each function can be written as a linear combination of up to $L$ (generally non-linear) subfunctions. Each server computes a fraction $\gamma$ of the subfunctions, then communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. Our goal is to bound the ratio between the computation workload done by all servers over the number of datasets. To this end, we here reformulate the real-valued distributed computing problem into a matrix factorization problem and then into a basic sparse recovery problem, where sparsity implies computational savings. Building on this, we first give a simple probabilistic scheme for subfunction assignment, which allows us to upper bound the optimal normalized computation cost as $\gamma \leq \frac{K}{N}$ that a generally intractable $\ell_0$-minimization would give. To bypass the intractability of such optimal scheme, we show that if these optimal schemes enjoy $\gamma \leq - r\frac{K}{N}W^{-1}_{-1}(- \frac{2K}{e N r} )$ (where $W_{-1}(\cdot)$ is the Lambert function and $r$ calibrates the communication between servers and users), then they can actually be derived using a tractable Basis Pursuit $\ell_1$-minimization. This newly-revealed connection between distributed computation and compressed sensing opens up the possibility of designing practical distributed computing algorithms by employing tools and methods from compressed sensing., Comment: Submitted to ITW2023. arXiv admin note: text overlap with arXiv:2206.11119

In this paper, we consider a coded caching scenario where users have heterogeneous interests. Taking into consideration the system model originally proposed by Wang and Peleato, for which the end-receiving users are divided into groups according to their file preferences, we develop a novel information-theoretic converse on the optimal worst-case communication load under uncoded cache placement. Interestingly, the developed converse bound, jointly with one of the coded schemes proposed by Wang and Peleato, allows us to characterize the optimal worst-case communication load under uncoded prefetching within a constant multiplicative gap of $2$. Although we restrict the caching policy to be uncoded, our work improves the previously known order optimality results for the considered caching problem., Comment: 6 pages. Accepted to 2022 IEEE Information Theory Workshop (ITW)

Coded distributed computing (CDC) is a new technique proposed with the purpose of decreasing the intense data exchange required for parallelizing distributed computing systems. Under the famous MapReduce paradigm, this coded approach has been shown to decrease this communication overhead by a factor that is linearly proportional to the overall computation load during the mapping phase. Nevertheless, it is widely accepted that this overhead remains a main bottleneck in distributed computing. To address this, we take a new approach and we explore a new system model which, for the same aforementioned overall computation load of the mapping phase, manages to provide astounding reductions of the communication overhead and, perhaps counterintuitively, a substantial increase of the computational parallelization. In particular, we propose multi-access distributed computing (MADC) as a novel generalization of the original CDC model, where now mappers and reducers are distinct computing nodes that are connected through a multi-access network topology. Focusing on the MADC setting with combinatorial topology, which implies $\Lambda$ mappers and $K$ reducers such that there is a unique reducer connected to any $\alpha$ mappers, we propose a novel coded scheme and a novel information-theoretic converse, which jointly identify the optimal inter-reducer communication load to within a constant gap of $1.5$. Additionally, a modified coded scheme and converse identify the optimal max-link communication load across all existing links to within a gap of $4$. The unparalleled coding gains reported here should not be simply credited to having access to more mapped data, but rather to the powerful role of topology in effectively aligning mapping outputs. This realization raises the open question of which multi-access network topology guarantees the best possible performance in distributed computing., Comment: 39 pages, 3 figures. Submitted to IEEE Transactions on Information Theory

In this work, we explore the problem of multi-user linearly-separable distributed computation, where $N$ servers help compute the desired functions (jobs) of $K$ users, and where each desired function can be written as a linear combination of up to $L$ (generally non-linear) subtasks (or sub-functions). Each server computes some of the subtasks, communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. We explore the computation and communication relationship between how many servers compute each subtask vs. how much data each user receives. For a matrix $\mathbf{F}$ representing the linearly-separable form of the set of requested functions, our problem becomes equivalent to the open problem of sparse matrix factorization $\mathbf{F} = \mathbf{D}\mathbf{E}$ over finite fields, where a sparse decoding matrix $\mathbf{D}$ and encoding matrix $\mathbf{E}$ imply reduced communication and computation costs respectively. This paper establishes a novel relationship between our distributed computing problem, matrix factorization, syndrome decoding and covering codes. To reduce the computation cost, the above $\mathbf{D}$ is drawn from covering codes or from a here-introduced class of so-called `partial covering' codes, whose study here yields computation cost results that we present., Comment: 57 pages, 5 figures. Submitted to IEEE Transactions on Information Theory

The recent introduction of vector coded caching has revealed that multi-rank transmissions in the presence of receiver-side cache content can dramatically ameliorate the file-size bottleneck of coded caching and substantially boost performance in error-free wire-like channels. We here employ large-matrix analysis to explore the effect of vector coded caching in realistic wireless multi-antenna downlink systems. Our analysis answers a simple question: Under a fixed set of antenna and SNR resources, and a given downlink MISO system which can already enjoy an optimized exploitation of multiplexing and beamforming gains, what is the multiplicative boost in the throughput when we are now allowed to occasionally add content inside reasonably-sized receiver-side caches? The derived closed-form expressions capture various linear precoders, and a variety of practical considerations such as power dissemination across signals, realistic SNR values, as well as feedback costs. The schemes are very simple (we simply collapse precoding vectors into a single vector), and the recorded gains are notable. For example, for 32 transmit antennas, a received SNR of 20 dB, a coherence bandwidth of 300 kHz, a coherence period of 40 ms, and under realistic file-size and cache-size constraints, vector coded caching is here shown to offer a multiplicative throughput boost of about 310% with ZF/RZF precoding and a 430% boost in the performance of already optimized MF-based systems. Interestingly, vector coded caching also accelerates channel hardening to the benefit of feedback acquisition, often surpassing 540% gains over traditional hardening-constrained downlink systems.

Recently, Muralidhar et al. proposed a novel multi-access system model where each user is connected to multiple caches in a manner that follows the well-known combinatorial topology of combination networks. For such multi-access topology, the same authors proposed an achievable scheme, which stands out for the unprecedented coding gains even with very modest cache resources. In this paper, we identify the fundamental limits of such multi-access setting with exceptional potential, providing an information-theoretic converse which establishes, together with the inner bound by Muralidhar et al., the exact optimal performance under uncoded prefetching., Comment: 5 pages, 1 figure. Submitted to 2022 IEEE International Symposium on Information Theory (ISIT). arXiv admin note: substantial text overlap with arXiv:2110.07426

In typical coded caching scenarios, the content of a central library is assumed to be of interest to all receiving users. However, in a realistic scenario the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, $40\,\%$ of the users and each user has potential interest in $40\,\%$ of the library? What if then each user caches selfishly only from content of potential interest? In this work, we formulate the symmetric selfish coded caching problem, where each user naturally makes requests from a subset of the library, which defines its own file demand set (FDS), and caches selfishly only contents from its own FDS. For the scenario where the different FDSs symmetrically overlap to some extent, we propose a novel information-theoretic converse that reveals, for such general setting of symmetric FDS structures, that selfish coded caching yields a load performance which is strictly worse than that in standard coded caching., Comment: 6 pages. Submitted to 2022 IEEE International Symposium on Information Theory (ISIT). arXiv admin note: substantial text overlap with arXiv:2109.04807

This work elevates coded caching networks from their purely information-theoretic framework to a stochastic setting, by exploring the effect of random user activity and by exploiting correlations in the activity patterns of different users. In particular, the work studies the $K$-user cache-aided broadcast channel with a limited number of cache states, and explores the effect of cache state association strategies in the presence of arbitrary user activity levels; a combination that strikes at the very core of the coded caching problem and its crippling subpacketization bottleneck. We first present a statistical analysis of the average worst-case delay performance of such subpacketization-constrained (state-constrained) coded caching networks, and provide computationally efficient performance bounds as well as scaling laws for any arbitrary probability distribution of the user-activity levels. The achieved performance is a result of a novel user-to-cache state association algorithm that leverages the knowledge of probabilistic user-activity levels. We then follow a data-driven approach that exploits the prior history on user-activity levels and correlations, in order to predict interference patterns, and thus better design the caching algorithm. This optimized strategy is based on the principle that users that overlap more, interfere more, and thus have higher priority to secure complementary cache states. This strategy is proven here to be within a small constant factor from the optimal. Finally, the above analysis is validated numerically using synthetic data following the Pareto principle. To the best of our understanding, this is the first work that seeks to exploit user-activity levels and correlations, in order to map future interference and design optimized coded caching algorithms that better handle this interference.

This work studies the $K$-user broadcast channel with $\Lambda$ caches, when the association between users and caches is random, i.e., for the scenario where each user can appear within the coverage area of -- and subsequently is assisted by -- a specific cache based on a given probability distribution. Caches are subject to a cumulative memory constraint that is equal to $t$ times the size of the library. We provide a scheme that consists of three phases: the storage allocation phase, the content placement phase, and the delivery phase, and show that an optimized storage allocation across the caches together with a modified uncoded cache placement and delivery strategy alleviates the adverse effect of cache-load imbalance by significantly reducing the multiplicative performance deterioration due to randomness. In a nutshell, our work provides a scheme that manages to substantially mitigate the impact of cache-load imbalance in stochastic networks, as well as -- compared to the best-known state-of-the-art -- the well-known subpacketization bottleneck by showing its applicability in deterministic settings for which it achieves the same delivery time -- which was proven to be close to optimal for bounded values of $t$ -- with an exponential reduction in the subpacketization.

This work identifies the fundamental limits of Multi-Access Coded Caching (MACC) where each user is connected to multiple caches in a manner that follows a generalized combinatorial topology. This topology stands out as it allows for unprecedented coding gains, even with very modest cache resources. First, we extend the setting and the scheme presented by Muralidhar et al. to a much more general topology that supports both a much denser range of users and the coexistence of users connected to different numbers of caches, all while maintaining the astounding coding gains, here proven to be exactly optimal, associated with the combinatorial topology. This is achieved, for this generalized topology, with a novel information-theoretic converse that we present here, which establishes, together with the scheme, the exact optimal performance under the assumption of uncoded placement. We subsequently consider different connectivity ensembles, including the very general scenario of the entire ensemble of all possible network connectivities/topologies, where any user can be connected to any subset of caches arbitrarily. For these settings, we develop novel converse bounds on the optimal performance averaged over the ensemble's different connectivities, considering the additional realistic scenario that the connectivity at delivery time is entirely unknown during cache placement. This novel analysis of topological ensembles leaves open the possibility that currently-unknown topologies may yield even higher gains, a hypothesis that is part of the bigger question of which network topology yields the most caching gains., Comment: 48 pages, 2 figures. Submitted to IEEE Transactions on Information Theory

The original coded caching scenario assumes a content library that is of interest to all receiving users. In a realistic scenario though, the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, $40\,\%$ of the users and each user has potential interest in $40\,\%$ of the library? In this work, we investigate the so-called symmetrically selfish coded caching scenario, where each user only makes requests from a subset of the library that defines its own File Demand Set (FDS), each user caches selfishly only contents from its own FDS, and where the different FDSs symmetrically overlap to some extent. In the context of various traditional prefetching scenarios (prior to the emergence of coded caching), selfish approaches were known to be potentially very effective. On the other hand, with the exception of some notable works, little is known about selfish coded caching. We here present a new information-theoretic converse that proves, in a general setting of symmetric FDS structures, that selfish coded caching, despite enjoying a much larger local caching gain and a much smaller set of possible demands, introduces an unbounded load increase compared to the unselfish case. In particular, in the $K$-user broadcast channel where each user stores a fraction $\gamma$ of the library, where each file (class) is of interest to $\alpha$ users, and where any one specific file is of interest to a fraction $\delta$ of users, the optimal coding gain of symmetrically selfish caching is at least $(K - \alpha)\gamma + 1$ times smaller than in the unselfish scenario. This allows us to draw the powerful conclusion that the optimal selfish coding gain is upper bounded by $1/(1 - \delta)$, and thus does not scale with $K$. These derived limits are shown to be exact for different types of demands., Comment: 48 pages, 8 figures. Submitted to IEEE Transactions on Information Theory

This work presents a new way of exploiting non-uniform file popularity in coded caching networks. Focusing on a fully-connected fully-interfering wireless setting with multiple cache-enabled transmitters and receivers, we show how non-uniform file popularity can be used very efficiently to accelerate the impact of transmitter-side data redundancy on receiver-side coded caching. This approach is motivated by the recent discovery that, under any realistic file-size constraint, having content appear in multiple transmitters can in fact dramatically boost the speed-up factor attributed to coded caching. We formulate an optimization problem that exploits file popularity to optimize the placement of files at the transmitters. We then provide a proof that reduces significantly the variable search space, and propose a new search algorithm that solves the problem at hand. We also prove an analytical performance upper bound, which is in fact met by our algorithm in the regime of many receivers. Our work reflects the benefits of allocating higher cache redundancy to more popular files, but also reflects a law of diminishing returns where for example very popular files may in fact benefit from minimum redundancy. In the end, this work reveals that in the context of coded caching, employing multiple transmitters can be a catalyst in fully exploiting file popularity, as it avoids various asymmetry complications that appear when file popularity is used to alter the receiver-side cache placement., Comment: 14 pages, submitted to Transactions on Networking

We address the worst-user bottleneck of wireless coded caching, which is known to severely diminish cache-aided multicasting gains due to the fundamental worst-channel limitation of multicasting transmission. We consider the quasi-static Rayleigh fading Broadcast Channel, for which we first show that the effective coded caching gain of the XOR-based standard coded-caching scheme completely vanishes in the low-SNR regime. Then, we reveal that this collapse is not intrinsic to coded caching. We do so by presenting a novel scheme that can fully recover the coded caching gains by capitalizing on one aspect that has to date remained unexploited: the shared side information brought about by the effectively unavoidable file-size constraint. As a consequence, the worst-user effect is dramatically ameliorated, as it is substituted by a much more subtle worst-group-of-users effect, where the suggested grouping is fixed, and it is decided before the channel or the demands are known. In some cases, the theoretical gains are completely recovered, and this is done without any user selection technique. We analyze the achievable rate performance of the proposed scheme and derive insightful performance approximations which prove to be very precise.

One of the famous problems in communications was the so-called "PN" problem in the Broadcast Channel, which refers to the setting where a fixed set of users provide perfect Channel State Information (CSI) to a multi-antenna transmitter, whereas the remaining users only provide finite-precision CSI or no CSI. The Degrees-of-Freedom (DoF) of that setting were recently derived by means of the Aligned Image Set approach. In this work, we resolve the cache-aided variant of this problem (i.e., the "PN" setting with side information) in the regime where the number of users providing perfect CSI is smaller or equal to the number of transmit antennas. In particular, we derive the optimal rate-memory trade-off under the assumption of uncoded placement and characterize the same trade-off within a factor of 2.01 for general placement. The result proves that the "PN" impact remains similar even in the presence of side information, but also that the optimal trade-off is not achievable through independently serving the two sets of users., Comment: Extended version of a paper presented in 2020 IEEE ITW

Multi-antenna coded caching is known to combine a global caching gain that is proportional to the cumulative cache size found across the network, with an additional spatial multiplexing gain that stems from using multiple transmitting antennas. However, a closer look reveals two severe bottlenecks; the well-known exponential subpacketization bottleneck that dramatically reduces performance when the communicated file sizes are finite, and the considerable optimization complexity of beamforming multicast messages when the SNR is finite. We here present an entirely novel caching scheme, termed \emph{cyclic multi-antenna coded caching}, whose unique structure allows for the resolution of the above bottlenecks in the crucial regime of many transmit antennas. For this regime, where the multiplexing gain can exceed the coding gain, our new algorithm is the first to achieve the exact one-shot linear optimal DoF with a subpacketization complexity that scales only linearly with the number of users, and the first to benefit from a multicasting structure that allows for exploiting uplink-downlink duality in order to yield optimized beamformers ultra-fast. In the end, our novel solution provides excellent performance for networks with finite SNR, finite file sizes, and many users.

The work establishes the exact performance limits of stochastic coded caching when users share a bounded number of cache states, and when the association between users and caches, is random. Under the premise that more balanced user-to-cache associations perform better than unbalanced ones, our work provides a statistical analysis of the average performance of such networks, identifying in closed form, the exact optimal average delivery time. To insightfully capture this delay, we derive easy to compute closed-form analytical bounds that prove tight in the limit of a large number $\Lambda$ of cache states. In the scenario where delivery involves $K$ users, we conclude that the multiplicative performance deterioration due to randomness -- as compared to the well-known deterministic uniform case -- can be unbounded and can scale as $\Theta\left( \frac{\log \Lambda}{\log \log \Lambda} \right)$ at $K=\Theta\left(\Lambda\right)$, and that this scaling vanishes when $K=\Omega\left(\Lambda\log \Lambda\right)$. To alleviate this adverse effect of cache-load imbalance, we consider various load balancing methods, and show that employing proximity-bounded load balancing with an ability to choose from $h$ neighboring caches, the aforementioned scaling reduces to $\Theta \left(\frac{\log(\Lambda / h)}{ \log \log(\Lambda / h)} \right)$, while when the proximity constraint is removed, the scaling is of a much slower order $\Theta \left( \log \log \Lambda \right)$. The above analysis is extensively validated numerically., Comment: 40 pages, 12 figures

We consider cache-aided wireless communication scenarios where each user requests both a file from an a-priori generated cacheable library (referred to as 'content'), and an uncacheable 'non-content' message generated at the start of the wireless transmission session. This scenario is easily found in real-world wireless networks, where the two types of traffic coexist and share limited radio resources. We focus on single-transmitter, single-antenna wireless networks with cache-aided receivers, where the wireless channel is modelled by a degraded Gaussian broadcast channel (GBC). For this setting, we study the delay-rate trade-off, which characterizes the content delivery time and non-content communication rates that can be achieved simultaneously. We propose a scheme based on the separation principle, which isolates the coded caching and multicasting problem from the physical layer transmission problem. We show that this separation-based scheme is sufficient for achieving an information-theoretically order optimal performance, up to a multiplicative factor of 2.01 for the content delivery time, when working in the generalized degrees of freedom (GDoF) limit. We further show that the achievable performance is near-optimal after relaxing the GDoF limit, up to an additional additive factor of 2 bits per dimension for the non-content rates. A key insight emerging from our scheme is that in some scenarios considerable amounts of non-content traffic can be communicated while maintaining the minimum content delivery time, achieved in the absence of non-content messages; compliments of 'topological holes' arising from asymmetries in wireless channel gains., Comment: Accepted for publication in the IEEE Transactions on Information Theory

This work identifies the fundamental limits of cache-aided coded multicasting in the presence of the well-known `worst-user' bottleneck. This stems from the presence of receiving users with uneven channel capacities, which often forces the rate of transmission of each multicasting message to be reduced to that of the slowest user. This bottleneck, which can be detrimental in general wireless broadcast settings, motivates the analysis of coded caching over a standard Single-Input-Single-Output (SISO) Broadcast Channel (BC) with K cache-aided receivers, each with a generally different channel capacity. For this setting, we design a communication algorithm that is based on superposition coding that capitalizes on the realization that the user with the worst channel may not be the real bottleneck of communication. We then proceed to provide a converse that shows the algorithm to be near optimal, identifying the fundamental limits of this setting within a multiplicative factor of 4. Interestingly, the result reveals that, even if several users are experiencing channels with reduced capacity, the system can achieve the same optimal delivery time that would be achievable if all users enjoyed maximal capacity., Comment: 6 pages, 1 figure. The work will be presented at the 2020 International Zurich Seminar on Information and Communication

In this work, we study a large linear interference network with an equal number of transmitters and receivers, where each transmitter is connected to two subsequent receivers. Each transmitter has individual access to a backhaul link (fetching the equivalent of $M_{T}$ files), while each receiver can cache a fraction $\gamma$ of the library. We explore the tradeoff between the communication rate, backhaul load, and caching storage by designing algorithms that can harness the benefits of cooperative transmission in partially connected networks, while exploiting the advantages of multicast transmissions attributed to user caching. We show that receiver caching and fetching content from the backhaul are two resources that can simultaneously increase the delivery performance in synergistic ways. Specifically, an interesting outcome of this work is that user caching of a fraction $\gamma$ of the library can increase the per-user Degrees of Freedom (puDoF) by $\gamma$. Further, the results reveal significant savings in the backhaul load, even in the small cache size region. For example, the puDoF achieved using the pair $(M_{T}=8, \gamma=0)$ can also be achieved with the pairs $(M_{T}=4,\gamma=0.035)$ and $(M_{T}=2,\gamma=0.1)$, showing that even small caches can provide significant savings in the backhaul load., Comment: 8 pages, 2 figures, submitted to ISIT 2019

The work explores the fundamental limits of coded caching in heterogeneous networks where multiple ($N_0$) senders/antennas, serve different users which are associated (linked) to shared caches, where each such cache helps an arbitrary number of users. Under the assumption of uncoded cache placement, the work derives the exact optimal worst-case delay and DoF, for a broad range of user-to-cache association profiles where each such profile describes how many users are helped by each cache. This is achieved by presenting an information-theoretic converse based on index coding that succinctly captures the impact of the user-to-cache association, as well as by presenting a coded caching scheme that optimally adapts to the association profile by exploiting the benefits of encoding across users that share the same cache. The work reveals a powerful interplay between shared caches and multiple senders/antennas, where we can now draw the striking conclusion that, as long as each cache serves at least $N_0$ users, adding a single degree of cache-redundancy can yield a DoF increase equal to $N_0$, while at the same time --- irrespective of the profile --- going from 1 to $N_0$ antennas reduces the delivery time by a factor of $N_0$. Finally some conclusions are also drawn for the related problem of coded caching with multiple file requests., Comment: arXiv admin note: substantial text overlap with arXiv:1809.09422

Multi-antenna cache-aided wireless networks have been known to suffer from a severe feedback bottleneck, where achieving the maximal Degrees-of-Freedom (DoF) performance required feedback from all served users. These costs matched the caching gains and thus scaled with the number of users. In the context of the $L$-antenna MISO broadcast channel with $K$ receivers having normalized cache size $\gamma$, we pair a fundamentally novel algorithm together with a new information-theoretic converse, and identify the optimal tradeoff between feedback costs and DoF performance, by showing that having CSIT from only $C

The work identifies the fundamental limits of coded caching when the K receiving users share {\Lambda}$\leq$ K helper-caches, each assisting an arbitrary number of different users. The main result is the derivation of the exact optimal worst-case delivery time - under the assumption of uncoded cache placement - for any user-to-cache association profile, where each such profile describes how many users are helped by each cache. This is achieved with a new information-theoretic converse that is based on index coding and which proves that a simple XOR-shrinking-and-removal coded-caching scheme is optimal irrespective of the user-to-cache association profile. All the results also apply directly to the coded caching problem with multiple file requests.

Within the context of coded caching, the work reveals the interesting connection between having multiple transmitters and having heterogeneity in the cache sizes of the receivers. Our work effectively shows that having multiple transmit antennas -- while providing full multiplexing gains -- can also simultaneously completely remove the performance penalties that are typically associated to cache-size unevenness. Focusing on the multiple-input single-output Broadcast Channel, the work first identifies the performance limits of the extreme case where cache-aided users coincide with users that do not have caches, and then expands the analysis to the case where both user groups are cache-aided but with heterogeneous cache-sizes. In the first case, the main contribution is a new algorithm that employs perfect matchings on a bipartite graph to offer full multiplexing as well as full coded-caching gains to both cache-aided as well as cache-less users. An interesting conclusion is that, starting from a single-stream centralized coded caching setting with normalized cache size $\gamma$, then adding $L$ antennas allows for the addition of {up to} approximately $L/\gamma$ extra cache-less users, at no added delay costs. Similarly surprising is the finding that, {beginning} with a single-antenna hybrid system (with both cache-less and cache-aided users), then adding {$L-1$} antennas to the transmitter, as well as endowing the cache-less users with a cumulative normalized cache size $\Gamma_2$, increases the Degrees of Freedom by a \emph{multiplicative} factor of up to $\Gamma_{2}+L$., Comment: 17 pages, partially presented in ITW 2018, Accepted for publication in Transactions on Information Theory

This work explores a distributed computing setting where $K$ nodes are assigned fractions (subtasks) of a computational task in order to perform the computation in parallel. In this setting, a well-known main bottleneck has been the inter-node communication cost required to parallelize the task, because unlike the computational cost which could keep decreasing as $K$ increases, the communication cost remains approximately constant, thus bounding the total speedup gains associated to having more computing nodes. This bottleneck was substantially ameliorated by the recent introduction of coded MapReduce techniques which allowed each node --- at the computational cost of having to preprocess approximately $t$ times more subtasks --- to reduce its communication cost by approximately $t$ times. In reality though, the associated speed up gains were severely limited by the requirement that larger $t$ and $K$ necessitated that the original task be divided into an extremely large number of subtasks. In this work we show how node cooperation, along with a novel assignment of tasks, can help to dramatically ameliorate this limitation. The result applies to wired as well as wireless distributed computing, and it is based on the idea of having groups of nodes compute identical parallelization (mapping) tasks and then employing a here-proposed novel D2D coded caching algorithm., Comment: 6 pages, 1 figure, submitted to ISIT 2018

In the context of coded caching in the $K$-user BC, our work reveals the surprising fact that having multiple ($L$) transmitting antennas, dramatically ameliorates the long-standing subpacketization bottleneck of coded caching by reducing the required subpacketization to approximately its $L$th root, thus boosting the actual DoF by a multiplicative factor of up to $L$. In asymptotic terms, this reveals that as long as $L$ scales with the theoretical caching gain, then the full cumulative (multiplexing + full caching) gains are achieved with constant subpacketization. This is the first time, in any known setting, that unbounded caching gains appear under finite file-size constraints. The achieved caching gains here are up to $L$ times higher than any caching gains previously experienced in any single- or multi-antenna fully-connected setting, thus offering a multiplicative mitigation to a subpacketization problem that was previously known to hard-bound caching gains to small constants. The proposed scheme is practical and it works for all values of $K,L$ and all cache sizes. The scheme's gains show in practice: e.g. for $K=100$, when $L=1$ the theoretical caching gain of $G=10$, under the original coded caching algorithm, would have needed subpacketization $S_1 = \binom{K}{G}= \binom{100}{10} > 10^{13}$, while if extra transmitting antennas were added, the subpacketization was previously known to match or exceed $S_1$. Now for $L=5$, our scheme offers the theoretical (unconstrained) cumulative DoF $d_L = L+G = 5+10=15$, with subpacketization $S_L=\binom{K/L}{G/L} =\binom{100/5}{10/5} = 190$. The work extends to the multi-server and cache-aided IC settings, while the scheme's performance, given subpacketization $S_L=\binom{K/L}{G/L}$, is within a factor of 2 from the optimal linear sum-DoF., Comment: 29 pages

We explore the performance of coded caching in a SISO BC setting where some users have higher link capacities than others. Focusing on a binary and fixed topological model where strong links have a fixed normalized capacity 1, and where weak links have reduced normalized capacity $\tau<1$, we identify --- as a function of the cache size and $\tau$ --- the optimal throughput performance, within a factor of at most 8. The transmission scheme that achieves this performance, employs a simple form of interference enhancement, and exploits the property that weak links attenuate interference, thus allowing for multicasting rates to remain high even when involving weak users. This approach ameliorates the negative effects of uneven topology in multicasting, now allowing all users to achieve the optimal performance associated to $\tau=1$, even if $\tau$ is approximately as low as $\tau\geq 1-(1-w)^g$ where $g$ is the coded-caching gain, and where $w$ is the fraction of users that are weak. This leads to the interesting conclusion that for coded multicasting, the weak users need not bring down the performance of all users, but on the contrary to a certain extent, the strong users can lift the performance of the weak users without any penalties on their own performance. Furthermore for smaller ranges of $\tau$, we also see that achieving the near-optimal performance comes with the advantage that the strong users do not suffer any additional delays compared to the case where $\tau = 1$., Comment: 7 pages, 4 figures

This work explores coded caching in the symmetric $K$-user cache-aided MISO BC with imperfect CSIT-type feedback, for the specific case where the cache size is much smaller than the library size. Building on the recently explored synergy between caching and delayed-CSIT, and building on the tradeoff between caching and CSIT quality, the work proposes new schemes that boost the impact of small caches, focusing on the case where the cumulative cache size is smaller than the library size. For this small-cache setting, based on the proposed near-optimal schemes, the work identifies the optimal cache-aided degrees-of-freedom (DoF) performance within a factor of 4., Comment: 8 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:1511.03961

In this paper, we consider the $K$-user cache-aided wireless MISO broadcast channel (BC) with random fading and delayed CSIT, and identify the optimal cache-aided degrees-of-freedom (DoF) performance within a factor of 4. The achieved performance is due to a scheme that combines basic coded-caching with MAT-type schemes, and which efficiently exploits the prospective-hindsight similarities between these two methods. This delivers a powerful synergy between coded caching and delayed feedback, in the sense that the total synergistic DoF-gain can be much larger than the sum of the individual gains from delayed CSIT and from coded caching. The derived performance interestingly reveals --- for the first time --- substantial DoF gains from coded caching, even when the (normalized) cache size $\gamma$ (fraction of the library stored at each receiving device) is very small. Specifically, a microscopic $\gamma \approx e^{-G}$ can come within a factor of $G$ from the interference-free optimal. For example, storing at each device only a \emph{thousandth} of what is deemed as `popular' content ($\gamma\approx 10^{-3}$), we approach the interference-free optimal within a factor of $ln(10^3) \approx 7$ (per user DoF of $1/7$), for any number of users. This result carries an additional practical ramification as it reveals how to use coded caching to essentially buffer CSI, thus partially ameliorating the burden of having to acquire real-time CSIT., Comment: 7 pages. Smaller part from a bigger journal submission arXiv:1511.03961

This work studies the optimal Degrees-of-Freedom (DoF) of the $K$-User MISO Broadcast Channel (BC) with delayed Channel-State Information at the Transmitter (CSIT) and with additional current noisy CSIT where the current channel estimation error scales in~$P^{-\alpha}$ for $\alpha\in[0,1]$. This papers establishes for the first time the optimal DoF in this setting thanks to a new transmission scheme which achieves the elusive DoF-optimal combining of the Maddah-Ali and Tse scheme (MAT) introduced in their seminal work in $2010$ with Zero-Forcing (ZF) for an arbitrary number of users. The derived sum DoF takes the surprisingly simple form $(1-\alpha) K/H_K+\alpha K$ where $H_K\triangleq \sum_{k=1}^K \frac{1}{k}$ is the sum-DoF achieved using solely MAT., Comment: Submitted to IEEE Transaction on Information Theory

Building on the recent coded-caching breakthrough by Maddah-Ali and Niesen, the work here considers the $K$-user cache-aided wireless multi-antenna (MISO) symmetric broadcast channel (BC) with random fading and imperfect feedback, and analyzes the throughput performance as a function of feedback statistics and cache size. In this setting, our work identifies the optimal cache-aided degrees-of-freedom (DoF) within a factor of 4, by identifying near-optimal schemes that exploit the new synergy between coded caching and delayed CSIT, as well as by exploiting the unexplored interplay between caching and feedback-quality. The derived limits interestingly reveal that --- the combination of imperfect quality current CSIT, delayed CSIT, and coded caching, guarantees that --- the DoF gains have an initial offset defined by the quality of current CSIT, and then that the additional gains attributed to coded caching are exponential, in the sense that any linear decrease in the required DoF performance, allows for an exponential reduction in the required cache size., Comment: 14 pages, 2 figures, submission Trans IT, V2

This work explores the rate-reliability-complexity limits of the quasi-static K-user multiple access channel (MAC), with or without feedback. Using high-SNR asymptotics, the work first derives bounds on the computational resources required to achieve near-optimal (ML-based) decoding performance. It then bounds the (reduced) complexity needed to achieve any (including suboptimal) diversity-multiplexing performance tradeoff (DMT) performance, and finally bounds the same complexity, in the presence of feedback-aided user selection. This latter effort reveals the ability of a few bits of feedback not only to improve performance, but also to reduce complexity. In this context, the analysis reveals the interesting finding that proper calibration of user selection can allow for near-optimal ML-based decoding, with complexity that need not scale exponentially in the total number of codeword bits. The derived bounds constitute the best known performance-vs-complexity behavior to date for ML-based MAC decoding, as well as a first exploration of the complexity-feedback-performance interdependencies in multiuser settings., Comment: submitted to IEEE Transactions on Signal Processing for publication

In many wireless networks, link strengths are affected by many topological factors such as different distances, shadowing and inter-cell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects has remained largely unexplored, despite strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. The work here takes a step in exploring this interplay between topology, feedback and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong vs. weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter (alternating CSIT) where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management (TSM) schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort --- of channel learning and feeding back CSIT --- for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users., Comment: Shorter version will be presented at ISIT 2014

Extending recent findings on the two-user MISO broadcast channel (BC) with imperfect and delayed channel state information at the transmitter (CSIT), the work here explores the performance of the two user MIMO BC and the two user MIMO interference channel (MIMO IC), in the presence of feedback with evolving quality and timeliness. Under standard assumptions, and in the presence of M antennas per transmitter and N antennas per receiver, the work derives the DoF region, which is optimal for a large regime of sufficiently good (but potentially imperfect) delayed CSIT. This region concisely captures the effect of having predicted, current and delayed-CSIT, as well as concisely captures the effect of the quality of CSIT offered at any time, about any channel. In addition to the progress towards describing the limits of using such imperfect and delayed feedback in MIMO settings, the work offers different insights that include the fact that, an increasing number of receive antennas can allow for reduced quality feedback, as well as that no CSIT is needed for the direct links in the IC., Comment: This paper will be presented in part at SPAWC13

For the two-user MISO broadcast channel with imperfect and delayed channel state information at the transmitter (CSIT), the work explores the tradeoff between performance on the one hand, and CSIT timeliness and accuracy on the other hand. The work considers a broad setting where communication takes place in the presence of a random fading process, and in the presence of a feedback process that, at any point in time, may provide CSIT estimates - of some arbitrary accuracy - for any past, current or future channel realization. This feedback quality may fluctuate in time across all ranges of CSIT accuracy and timeliness, ranging from perfectly accurate and instantaneously available estimates, to delayed estimates of minimal accuracy. Under standard assumptions, the work derives the degrees-of-freedom (DoF) region, which is tight for a large range of CSIT quality. This derived DoF region concisely captures the effect of channel correlations, the accuracy of predicted, current, and delayed-CSIT, and generally captures the effect of the quality of CSIT offered at any time, about any channel. The work also introduces novel schemes which - in the context of imperfect and delayed CSIT - employ encoding and decoding with a phase-Markov structure. The results hold for a large class of block and non-block fading channel models, and they unify and extend many prior attempts to capture the effect of imperfect and delayed feedback. This generality also allows for consideration of novel pertinent settings, such as the new periodically evolving feedback setting, where a gradual accumulation of feedback bits progressively improves CSIT as time progresses across a finite coherence period., Comment: Accepted to IEEE Trans. Inf. Theory. This paper was presented in part at the 50th Annual Allerton Conference 2012, at ITA-UCSD 2013, and at ISIT 2013

In the setting of the time-selective two-user multiple-input single-output (MISO) broadcast channel (BC), recent work by Tandon et al. considered the case where - in the presence of error-free delayed channel state information at the transmitter (delayed CSIT) - the current CSIT for the channel of user 1 and of user 2, alternate between the two extreme states of perfect current CSIT and of no current CSIT. Motivated by the problem of having limited-capacity feedback links which may not allow for perfect CSIT, as well as by the need to utilize any available partial CSIT, we here deviate from this `all-or-nothing' approach and proceed - again in the presence of error-free delayed CSIT - to consider the general setting where current CSIT now alternates between any two qualities. Specifically for $I_1$ and $I_2$ denoting the high-SNR asymptotic rates-of-decay of the mean-square error of the CSIT estimates for the channel of user~1 and of user~2 respectively, we consider the case where $I_1,I_2 \in\{\gamma,\alpha\}$ for any two positive current-CSIT quality exponents $\gamma,\alpha$. In a fast-fading setting where we consider communication over any number of coherence periods, and where each CSIT state $I_1I_2$ is present for a fraction $\lambda_{I_1I_2}$ of this total duration, we focus on the symmetric case of $\lambda_{\alpha\gamma}=\lambda_{\gamma\alpha}$, and derive the optimal degrees-of-freedom (DoF) region. The result, which is supported by novel communication protocols, naturally incorporates the aforementioned `Perfect current' vs. `No current' setting by limiting $I_1,I_2\in\{0,1\}$. Finally, motivated by recent interest in frequency correlated channels with unmatched CSIT, we also analyze the setting where there is no delayed CSIT.

This work considers the multiuser multiple-input single-output (MISO) broadcast channel (BC), where a transmitter with M antennas transmits information to K single-antenna users, and where - as expected - the quality and timeliness of channel state information at the transmitter (CSIT) is imperfect. Motivated by the fundamental question of how much feedback is necessary to achieve a certain performance, this work seeks to establish bounds on the tradeoff between degrees-of-freedom (DoF) performance and CSIT feedback quality. Specifically, this work provides a novel DoF region outer bound for the general K-user MISO BC with partial current CSIT, which naturally bridges the gap between the case of having no current CSIT (only delayed CSIT, or no CSIT) and the case with full CSIT. The work then characterizes the minimum CSIT feedback that is necessary for any point of the sum DoF, which is optimal for the case with M >= K, and the case with M=2, K=3., Comment: An initial version of this paper has been reported as Research Report No. RR-12-275 at EURECOM, December 7, 2012. This paper was submitted in part to the ISIT 2013

The work considers the two-user MISO broadcast channel with gradual and delayed accumulation of channel state information at the transmitter (CSIT), and addresses the question of how much feedback is necessary, and when, in order to achieve a certain degrees-of-freedom (DoF) performance. Motivated by limited-capacity feedback links that may not immediately convey perfect CSIT, and focusing on the block fading scenario, we consider a progressively increasing CSIT quality as time progresses across the coherence period (T channel uses - evolving current CSIT), or at any time after (delayed CSIT). Specifically, for any set of feedback quality exponents a_t, t=1,...,T, describing the high-SNR rates-of-decay of the mean square error of the current CSIT estimates at time t<=T (during the coherence period), the work describes the optimal DOF region in several different evolving CSIT settings, including the setting with perfect delayed CSIT, the asymmetric setting where the quality of feedback differs from user to user, as well as considers the DoF region in the presence of a imperfect delayed CSIT corresponding to having a limited number of overall feedback bits. These results are supported by novel multi-phase precoding schemes that utilize gradually improving CSIT. The approach here naturally incorporates different settings such as the perfect-delayed CSIT setting of Maddah-Ali and Tse, the imperfect current CSIT setting of Yang et al. and of Gou and Jafar, the asymmetric setting of Maleki et al., as well as the not-so-delayed CSIT setting of Lee and Heath., Comment: Submitted to Transactions on Information Theory - November 2012 18 double column pages

In the setting of the two-user broadcast channel, where a two-antenna transmitter communicates information to two single-antenna receivers, recent work by Maddah-Ali and Tse has shown that perfect knowledge of delayed channel state information at the transmitter (perfect delayed CSIT) can be useful, even in the absence of any knowledge of current CSIT. Similar benefits of perfect delayed CSIT were revealed in recent work by Kobayashi et al., Yang et al., and Gou and Jafar, which extended the above to the case of perfect delayed CSIT and imperfect current CSIT. The work here considers the general problem of communicating, over the aforementioned broadcast channel, with imperfect delayed and imperfect current CSIT, and reveals that even substantially degraded and imperfect delayed-CSIT is in fact sufficient to achieve the aforementioned gains previously associated to perfect delayed CSIT. The work proposes novel multi-phase broadcasting schemes that properly utilize knowledge of imperfect delayed and imperfect current CSIT, to match in many cases the optimal degrees-of-freedom (DoF) region achieved with perfect delayed CSIT. In addition to the theoretical limits and explicitly constructed precoders, the work applies towards gaining practical insight as to when it is worth improving CSIT quality., Comment: arXiv admin note: substantial text overlap with arXiv:1205.3474

In the setting of the two-user broadcast channel, recent work by Maddah-Ali and Tse has shown that knowledge of prior channel state information at the transmitter (CSIT) can be useful, even in the absence of any knowledge of current CSIT. Very recent work by Kobayashi et al., Yang et al., and Gou and Jafar, extended this to the case where, instead of no current CSIT knowledge, the transmitter has partial knowledge, and where under a symmetry assumption, the quality of this knowledge is identical for the different users' channels. Motivated by the fact that in multiuser settings, the quality of CSIT feedback may vary across different links, we here generalize the above results to the natural setting where the current CSIT quality varies for different users' channels. For this setting we derive the optimal degrees-of-freedom (DoF) region, and provide novel multi-phase broadcast schemes that achieve this optimal region. Finally this generalization incorporates and generalizes the corresponding result in Maleki et al. which considered the broadcast channel with one user having perfect CSIT and the other only having prior CSIT.