The introduction of the new multi-user linearly-separable distributed computing framework, has recently revealed how a parallel treatment of users can yield large parallelization gains with relatively low computation and communication costs. These gains stem from a new approach that converts the computing problem into a sparse matrix factorization problem; a matrix \(\mathbf{F}\) that describes the users' requests, is decomposed as \(\mathbf{F} = \mathbf{DE}\), where a \(γ\)-sparse \(\mathbf{E}\) defines the task allocation across \(N\) servers, and a \(δ\)-sparse \(\mathbf{D}\) defines the connectivity between \(N\) servers and \(K\) users as well as the decoding process. While this approach provides near-optimal performance, its linear nature has raised data secrecy concerns. We adopt an information-theoretic secrecy framework requiring that each user learns nothing more than its own requested function. Our main results provide (i) a necessary condition stating that for each user $k$ observing \(α_k\) server responses, the common randomness visible to that user must span a subspace of dimension greater than \(α_k-1\), and (ii) a necessary and sufficient condition requiring that removing from \(\mathbf{D}\) the columns corresponding to the servers observed by a user leaves a matrix of rank at least \(K-1\). Based on these conditions, we design a general, cost-preserving secrecy-enforcing transformation valid over both finite and real fields, obtained by appending to \(\mathbf{E}\) a basis of \(\mathrm{Null}(\mathbf{D})\) and carefully injecting shared randomness. This scheme preserves communication and computation costs, guarantees perfect information-theoretic secrecy over finite fields, and in the real case yields an explicit mutual-information bound that can be made arbitrarily small by increasing the variance of Gaussian common randomness.

This paper considers an $N$-server distributed computing setting with $K$ users requesting functions that are arbitrary multivariable polynomial evaluations of $L$ real (potentially non-linear) basis subfunctions, where each function output is raised to a bounded power. Our aim is to seek efficient task allocation and data communication techniques that reduce computation and communication costs. To this end, we take a tensor-theoretic approach, in which we represent the requested non-linearly decomposable functions using a properly designed tensor $\bar{\mathcal{F}}$, whose sparse decomposition into a tensor $\bar{\mathcal{E}}$ and a matrix $\mathbf{D}$ directly defines the task assignment, connectivity, and communication patterns. We design a lossless achievable scheme that integrates fixed-support SVD-based tensor factorization with multi-dimensional tiling of $\bar{\mathcal{E}}$ and $\mathbf{D}$, followed by a bipartite graph matching-based recursive assignment of tiles. This step transforms an overlapping decomposition into a disjoint one and reduces the resulting sum rank of the tiles, thereby decreasing the number of required servers. Under mild dimensionality conditions, we derive an explicit zero-error characterization of the achievable system rate $K/N$. Numerical simulations demonstrate the computational and communication savings over existing state-of-the-art matrix factorization approaches across a wide range of system parameters.

We consider a distributed computing system in which a master node coordinates $N$ workers to evaluate a function over $n$ input files, where this function accepts general decomposition. In particular, we focus on the general case where the requested function admits a $d$-uniform decomposition, meaning that it can be decomposed into a set of subfunctions that each depends on a unique $d$-tuple of the $n$ files. Our objective is to design file and task allocations that minimize the worst-case communication from the master to any worker and the worst-case computational load across workers. We first show that the optimal file and task allocation with minimum communication and computation costs admits a natural characterization within combinatorial design theory: it corresponds to a Steiner system $S(t, k, v)$ with $t=d$, $v=n$, and $k \approx \frac{n}{N^{1/d}}$. However, Steiner systems are known to exist only for very restricted parameter regimes. To overcome this limitation, we propose the information-theoretic-inspired \emph{Interweaved Clique (IC) design}, a universal and deterministic allocation framework that relaxes the strict structure of Steiner systems by allowing slight variations in worker file loads. Although slightly suboptimal, the IC design achieves a communication cost within a constant factor $4e$ from our converse, while also maintaining an order-optimal computation cost, thus allowing this work to derive the fundamental scaling laws of this general distributed computing problem for a large range of parameters.

This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $Δ$ users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given $K$, $L$, $M$, and $Δ$, we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments.

This work presents a first comprehensive analysis of the impact of vector coded caching (VCC) in multi-user multiple-input multiple-output (MU-MIMO) systems with multiple receive antennas and variable pathloss — two key factors that critically influence systems with inherent MU unicasting behavior. We investigate two widely adopted precoding strategies: (i) block-diagonalization (BD) at the transmitter combined with maximal ratio combining (MRC) at the receivers, and (ii) zero-forcing (ZF) precoding. Our analysis explicitly accounts for practical considerations such as channel fading, channel state information (CSI) acquisition overhead, and fairness-oriented power allocation. Our contributions span both analytical and simulation-based fronts. On the analytical side, we derive analytical expressions for the achievable throughput under BD-MRC and ZF, highlighting the performance benefits of equipping multi-antenna users with cache-aided interference management. Specifically, we develop a low-complexity BD-MRC optimization method that leverages matrix structure to significantly reduce the dimensionality involved in precoding computation, followed by solving the associated max-min fairness problem through an efficient one-dimensional search. In the massive MIMO regime, an asymptotic expression for the achievable throughput over Rayleigh fading channels is also derived. Simulations validate our theoretical results, confirming that VCC delivers substantial performance gains over optimized cacheless MU-MIMO systems. For example, with 32 transmit antennas and 2 receive antennas per user, VCC yields throughput improvements exceeding 300%. These gains are further amplified under imperfect CSI at the transmitter, where VCC’s ability to offload interference mitigation to the receivers ensures robust performance even in the face of degraded CSI quality and elevated acquisition costs.

Motivated by the wide-ranging applications of Hamiltonian decompositions in distributed computing, coded caching, routing, resource allocation, load balancing, and fault tolerance, our work presents a comprehensive design for Hamiltonian decompositions of complete k-uniform hypergraphs$K_{n}^{k}$. Building upon the resolution of the long-standing conjecture of the existence of Hamiltonian decompositions of complete hypergraphs — a problem that was resolved using existence-based methods — our contribution goes beyond the previous explicit designs, which were confined to the specific cases of$k=2$and$k=3$, by providing explicit designs for all$k$and$n$prime, allowing for a broad applicability of Hamiltonian decompositions in various settings.

We propose a new class of coded caching schemes for wireless networks, which we term as non-orthogonal multiple access (NOMA) aided aggregated coded caching (NACC), which manages to alleviate both the uneven channel bottleneck as well as the shared-cache limitation. In particular, NACC uses an aggregation principle to efficiently serve users with unequal channel strengths, as well as uses for the first time the NOMA principle to simultaneously transmit to multiple users that share the same exact cache state. This transmission strategy represents an efficient utilization of NOMA within the coded caching framework. We analyze the high-SNR transmission performance of the proposed scheme and derive analytical expressions for the achievable rate and the effective gain, providing a qualitative understanding of its spectral efficiency. Our numerical results for urban Micro-cell environments abiding by$5\mathrm{G}$standards, demonstrate that NACC achieves - with a single transmit antenna - the same spectral efficiency as a multi-user (MU) multicasting system with 32 transmit antennas, while it also matches the spectral efficiency of traditional MU unicasting system with 8 transmit antennas.

This paper studies a multiaccess coded caching (MACC) problem where the connectivity topology between the users and the caches can be described by a class of combinatorial designs. Our model includes several MACC topologies considered in previous works as special cases. The considered MACC network includes a server containingNfiles, Γ cache nodes andKcacheless users, where each user can accessLcache nodes. The server is connected to the users via an error-free shared link, while the users can directly access the content in their connected cache nodes. Our goal is to minimize 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, including the only cases where the number of usersKscales either linearly or exponentially in Γ. We overcome this limitation by formulating a new access topology derived from two classical combinatorial structures, referred to as thet-design and thet-group divisible design. By leveraging the properties of these 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. As a by-product, by extending the proposed scheme to the original dedicated coded caching scenario (i.e., each user has its own cache), the resulting scheme can unify several existing coded caching schemes.

The work considers theN-server distributed computing scenario withKusers requesting functions that are linearly-decomposable over an arbitrary basis ofLreal (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 ofKrequested 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 parameterT, representing the number of shots for each server — to minimize the reconstruction distortion$\frac {1}{KL}\|\mathbf {F} - \mathbf {D}\mathbf {E}\|^{2}_{F}$over all$\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 F into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of D and E. For the zero-error case and under basic dimensionality assumptions, the work reveals achievable computation-vs-communication corner points$(\gamma ,\delta)$which, for various cases, are proven optimal over a large class of$\mathbf {D},\mathbf {E}$by means of a novel tessellations-based converse. Subsequently, for largeN, and under basic statistical assumptions on F, the average achievable error$\epsilon $is concisely expressed using the incomplete first moment of the standard Marchenko-Pastur distribution, where this performance is shown to be optimal over a large class of D and E. In the end, the work also reveals that the overall achieved gains over baseline methods are unbounded.

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 F = DE, 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 F is decomposed into a parity check matrix D of a perfect code, and a matrix E which has columns as the coset leaders of this same code.

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. In this paper, we propose multi-access distributed computing (MADC) as a generalization of the original CDC model, where now mappers (nodes in charge of the map functions) and reducers (nodes in charge of the reduce functions) 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 coded scheme and an information-theoretic converse, which jointly identify the optimal inter-reducer communication load, as a function of the computation 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.

This work studies a well-known shared-cache coded caching scenario where each cache can serve an arbitrary number of users. We analyze 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.

This paper studies a novel multi-access coded caching (MACC) model where the topology between users and cache nodes is a generalization of those already studied in previous work, such as combinatorial and cross-resolvable design topologies. Our goal is to minimize the worst-case transmission load in the delivery phase from the server over all possible user requests. By formulating the access topology as two classical combinatorial structures, t-design and t-group divisible design, 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.

Coded distributed computing (CDC), originally proposed by Li et al., leverages coded multicast messages to exchange computed intermediate values among the distributed computing nodes, such that the overall communication load could be reduced by a factor of r, the number of input files assigned to each node. However, in the original CDC framework, each output function/task is composed of intermediate values from all input files. In this paper, we propose a new CDC problem for sparse functions with structured support, where each output function depends on a subset of the input files. For a symmetric structured support for which the input files are divided into G equal-length batches and each output function depends on the same number of G′batches, we propose a novel CDC scheme that is strictly better by a factor G/G′than directly employing the original CDC scheme in the considered problem. Furthermore, by proposing a new converse bound, we prove that the communication load of the proposed CDC scheme is order optimal within a constant multiplicative factor of 6.

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 γ 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 ℓ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}\left( { - \frac{{2K}}{{eNr}}} \right)$ (where W−1(•) is the Lambert function and r calibrates the communication between servers and users), then they can actually be derived using a tractable Basis Pursuit ℓ1-minimization. This newly-revealed connection opens up the possibility of designing practical distributed computing algorithms by employing tools and methods from compressed sensing.

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 subset of caches can serve any arbitrary number of users. For these settings, we develop novel converse bounds on the optimal performance averaged over the ensemble’s different connectivities. 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.

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. To then reduce the communication cost, these coding-theoretic properties are explored in the regime of codes that have low-density parity check matrices. The work reveals — first for the commonly used one-shot scenario — that in the limit of large$N$, the optimal normalized computation cost$\gamma \in (0,1)$is in the range$\gamma \in \left({H_{q}^{-1}\left({\frac {\log _{q}(L)}{N}}\right), H_{q}^{-1}(K/N)}\right)$— where$H_{q}$is the$q$-ary entropy function — and that this can be achieved with normalized communication cost that vanishes as$\sqrt {\log _{q}(N)}/N$. The above reveals an unbounded coding gain over the uncoded scenario, as well as reveals the role of a certain functional rate$\log _{q}(L)/N$and functional capacity$H_{q}(\gamma)$of the system. In the end, we also explore the multi-shot scenario, for which we derive bounds on the computation cost.

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 (i.e., the content stored at the cache of a certain user), 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 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. Consequently, we propose a search algorithm that solves the problem at hand while reducing the variable search space significantly. 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.

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. In this work, we employ large-matrix analysis to explore the effect of vector coded caching in realistic wireless multi-antenna downlink systems. For a given downlink MISO system already optimized to exploit both multiplexing and beamforming gains, and for a fixed set of antenna and SNR resources, our analysis answers a simple question: What is the multiplicative throughput boost obtained from introducing reasonably-sized receiver-side caches that can pre-store information content? 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 (cacheless) systems. Interestingly, vector coded caching also accelerates channel hardening to the benefit of feedback acquisition, often surpassing 540% gains over traditional hardening-constrained cacheless downlink systems.

We investigate the performance of coded caching in land mobile-satellite (LMS) systems, where a satellite station with full access to a content library serves K cache-aided land users. The promising gains that coded caching provides for the error-free shared-link Broadcast Channel are known to suffer in some low signal-to-noise ratio (SNR) scenarios. For this reason, we analyze to what extent the coded caching gains are preserved in LMS systems, which are governed by low-to-moderate SNR due to the long propagation distances. We model the satellite-terrestrial channels through the widely adopted Shadowed-Rician fading, and we show that the coded caching gains are partially preserved even in the low-SNR limit due to the existence of line-of-sight (LOS) components, which allows us to double the goodput of LMS communication at low SNR. These results illustrate the potential of coded caching in LMS systems and motivate further research to design adapted and practical coded caching schemes for LMS systems.

This work studies the K-user broadcast channel with Λ 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.

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 — in the non-trivial memory regime — than that in standard coded caching.

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.

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

In this work, we investigate the problem of multi-user linearly separable function computation, where N servers help compute the desired functions (jobs) of K users. In this setting each desired function can be written as a linear combination of up to L (generally non-linear) sub-functions. Each server computes some of the sub-tasks, and communicates a linear combination of its computed outputs (files) in a single-shot to some of the users, then each user linearly combines its received data in order to recover its desired function. We explore the range of the optimal computation cost via establishing a novel relationship between our problem, syndrome decoding and covering codes. The work reveals that in the limit of large N, the optimal computation cost — in the form of the maximum fraction of all servers that must compute any subfunction — is lower bounded as $\gamma \geq H_q^{ - 1}\left( {\frac{{{{\log }_q}(L)}}{N}} \right)$, for any fixed logq(L)/N. The result reveals the role of the computational rate logq(L)/N, which cannot exceed what one might call the computational capacity Hq(γ) of the system.

This work proposes a two-layered coded caching scheme to resolve the cache-load imbalance bottleneck of the coded caching in a stochastic shared-cache network where the association between users and shared 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-enabled helper node based on a uniform probability distribution. To insightfully capture the effectiveness of our scheme in mitigating the adverse effect of randomness in shared-cache networks, we derive the exact scaling laws of the average delivery time. In the scenario of an error-free broadcast channel of bounded capacity per unit of time where the delivery involves K users and Λ cache-enabled helper nodes, we show that empowering users with an additional layer of caching can significantly mitigate, and in certain memory regimes completely nullify the adverse effects of the cache-load imbalance bottleneck.

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. In the end, this work provides, in a unified manner, the strong conclusion that selfish caching can cause unbounded performance deterioration in coded caching systems.

Multi-antenna cache-aided wireless networks were thought to suffer from a severe feedback bottleneck, since achieving the maximal Degrees-of-Freedom (DoF) performance required feedback from all served users for the known transmission schemes. These feedback costs match the caching gains and thus scale with the number of users. In the context of the$L$-antenna Multiple-Input Single Output broadcast channel with$K$receivers, each 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 channel state information from only$C< L$served users implies an optimal one-shot linear DoF of$C+K\gamma $. As a side consequence of this, we also now understand that the well known DoF performance$L+K\gamma $is in fact exactly optimal. In practice, the above means that we are able to disentangle caching gains from feedback costs, thus achieving unbounded caching gains at the mere feedback cost of the multiplexing gain. This further solidifies the role of caching in boosting multi-antenna systems; caching now can provide unbounded DoF gains over multi-antenna downlink systems, at no additional feedback costs. The above results are extended to also include the corresponding multiple transmitter scenario with caches at both ends.

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. We consider the quasi-static Rayleigh fading Broadcast Channel, for which we first show that the effective coded caching gain of the standard XOR-based coded-caching scheme completely vanishes in the low signal-to-noise ratio (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 remained unexploited to date: 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. Furthermore, the theoretical gains are completely recovered as the number of users increases, and this is done without any user selection technique. We analyze the rate performance of the proposed scheme and derive approximations which prove to be very precise. Importantly, this novel approach can be translated to other coded caching schemes and scenarios, including decentralized scenarios.

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, termedcyclic multi-antennacoded 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 focuses on optimizing coded caching under asynchronous demands. We consider a single-stream setting where users are allowed to request content at arbitrary time-slots. Aiming to minimize the total system delay required to serve all users, i.e. from the moment of the first request to the delivery of the last bit of requested information, we design a pair of placement and delivery algorithms and show that the achievable performance is within a multiplicative factor of 2 from the optimal, under the assumption of uncoded placement, and within a multiplicative factor of 4.02 in the general placement case. Interesting characteristics of our algorithms are that i) a placement phase agnostic to the users' arrival times is adequate to provide a near-optimal delay, and ii) the proposed delivery algorithm requires low complexity and, at the same time, requires no non-causal information. Further, we show that systems are able to withstand some degree of asynchronicity without an increase in the delay compared to an equivalent synchronous setting. Finally, we highlight an interesting connection between coded caching under asynchronous demands and coded caching in wireless environments under uneven channel strengths.

We investigate the use of coded caching in the single-cell downlink scenario where the receiving users are randomly located inside the cell. We first show that, as a result of having users that experience very different path-loss, the real gain of the original coded caching scheme is severely reduced. We then prove that the use of shared caches - which, we stress, is a compulsory feature brought about by the subpacketization constraint in nearly every practical setting - introduces a spatial-averaging effect that allows us to recover most of the subpacketization-constrained gains that coded caching would have yielded in the error-free identical-link setting. For the ergodic-fading scenario with different pathloss, we derive tight approximations of the average (over the users) rate and of the coded caching gain by means of a basic high-SNR approximation on the point-to-point capacity. These derived expressions prove very accurate even for low SNR. We also provide a result based on the regime of large number of users which is nonetheless also valid for settings with few users. These results are extensively validated using Monte-Carlo simulations that adhere to 3GPP recommendations on system parameters for urban micro or macro cells.

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 Λ 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 Θ([log Λ]/[log log Λ]) at K = Θ(Λ ), and that this scaling vanishes when K = Ω(Λ log Λ ). 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 Θ([log(Λ/h)]/[log log(Λ/h)]) at K=Θ(Λ ), while when the proximity constraint is removed, the scaling is of a much slower order Θ(log log Λ ). The above analysis is extensively validated numerically.

The work establishes the exact fundamental limits of stochastic coded caching when users share a bounded number of cache states, and when the association between users and caches, is random. This association can greatly affect performance, which improves when the association is more balanced across the caches, and which deteriorates when this association becomes less uniform. Our work provides a statistical analysis of the average performance of such networks, quantifying the effect of randomness by identifying in closed-form, the exact optimal average delivery time. To insightfully capture this delay, we derive the exact scaling laws of the optimal average delivery time. 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 Θ([(logΛ )/(loglogΛ )]) at K=Θ(Λ), and that as K increases, this deterioration gradually reduces, and ceases to scale when K=Ω(ΛlogΛ). The above analysis is validated numerically.

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 communication 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 our investigation on single-transmitter 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 (normalized) 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 problem from the physical layer transmission problem, and prove its information-theoretic order optimality up to a multiplicative factor of 2.01. A key insight emerging from our scheme is that substantial 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.

This work considers the cache-aided multiple-input single-output broadcast channel (MISO BC) where an L-antenna transmitter serves K receiving users, each assisted by one of ΛKγ, all existing coded caching schemes suffer substantially reduced caching or multiplexing gains. Our work provides a novel coded caching scheme that achieves the exact best known, near optimal, DoF L+Kγ, and does so even if L > Kγ, thus covering an important hole in identifying the optimal performance for the multi-antenna shared-cache problem. Therefore, our work reveals that shared-cache systems with many transmit antennas can also enjoy both full multiplexing gains (L) as well as full caching gains (Kγ) despite the sharing of the caches. A side benefit of this scheme is its applicability in multi-antenna settings with dedicated users caches, where it can offer the advantage of reducing the subpacketization without sacrificing the DoF performance.

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 than 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 serving independently the two sets of users.

In this work, we address the worst-user bottleneck of coded caching, which is known to diminish any caching gains due to the fundamental requirement that the multicast transmission rate should be limited by that of the worst channel among the served users. We consider the quasi-static Rayleigh fading Broadcast Channel, for which we first show that the coded caching gain of the XOR-based standard coded-caching scheme completely vanishes in the low-SNR regime. Yet, we show that this collapse is not intrinsic to coded caching by presenting a novel scheme that can completely recover the caching gains. The scheme exploits an aspect that has remained unexploited: the shared side information brought about by the file size constraint. The worst-user effect is dramatically ameliorated because it is replaced by the worst-group-of-users effect, where the users within a group have the same side information and the grouping is decided before the channel or the demands are known.

This work identifies the optimal Degrees-ofFreedom (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-αfor α ∈ [0, 1]. These two settings had in the past been studied separately; the setting of imperfect current CSIT has attracted considerable interest over the last decade, while the setting of delayed CSIT was studied in the seminal work of Maddah-Ali and Tse in 2010 1 where an optimal DoF of K/ Σk=1K1/k was established. Since k=1 then there have been several efforts to combine the two settings of delayed and imperfect-current CSIT. Our work establishes for the first time the optimal DoF in this joint setting, capitalizing on a novel transmission scheme that is presented here, which combines a structurally new approach of handling past and current interference, to achieve the optimal performance. We establish the once elusive optimal DoF to be of the form 1 αK + (1 - α)K/(K/ Σk=1K1/k). This further shows that the two k=1 types of DoF gains, from current and delayed CSIT, can be combined additively.

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 -y, then adding L antennas allows for the addition of up to approximately L/γ 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 Γ2, increases the Degrees of Freedom by a multiplicative factor of up to Γ2+ L.

The work explores the fundamental limits of coded caching in the setting where a transmitter with potentially multiple (N0) antennas serves different users that are assisted by a smaller number of caches. 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 N0users, adding a single degree of cache-redundancy can yield a DoF increase equal to N0, while at the same time - irrespective of the profile - going from 1 to N0antennas reduces the delivery time by a factor of N0. Finally some conclusions are also drawn for the related problem of coded caching with multiple file requests.

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 MTfiles), while each receiver can cache a fraction γ 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 γ of the library can increase the per-user Degrees of Freedom (puDoF) by γ. 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 (MT= 8,γ = 0) can also be achieved with the pairs (MT= 4,γ = 0.035) and (MT= 2,γ = 0.1), showing that small caches can provide significant savings in the backhaul load.

The work considers a Coded MapReduce setting where computing nodes of different processing capabilities coexist. Motivated by scenarios where the mapping phase is performed by nodes of heterogeneous computing capabilities, we explore the setting with K1nodes that can each map a fraction γ1∈ [1/K,1] of the dataset, and K2nodes that can each map a smaller fraction γ21. For the standard wireless (single-antenna) device-to-device channel or its equivalent wired network with network-coding capabilities at the nodes, we propose a solution of assigning data to the nodes and a method of communicating intermediate values during the shuffling phase, that can be applied to any MapReduce problem and which entirely removes the affects of heterogeneity. The surprising outcome of this work is that the shuffling-phase delay is reduced by a factor of K1γ1+K2γ2, matching the performance of the corresponding homogeneous setting, thus revealing for the first time that heterogeneity during the mapping phase does not inherently deteriorate the overall performance.

The work studies the K -user shared-link broadcast channel with coded caching, where each user's file-request comes with a certain Quality-of-Service (QoS) requirement, thus allowing - in the context of multi-layered coding - users to download only those file layers that are necessary to meet their own QoS requirements. The work characterizes the exact optimal worst-case delivery time, under the assumption of uncoded cache placement that is oblivious to the individual QoS requirement of each user. The work derives a new index coding based information theoretic converse, which interestingly tells us exactly how to optimally cache.

This work studies the K-user broadcast channel where each user is assisted by one of Λ caches with a cumulative memory constraint that is equal to t times the size of the library, and where each cache serves an arbitrary number of users. In this setting, under the assumption of uncoded cache placement, no prior scheme is known to achieve a sum degrees of freedom (DoF) of t + 1, other than in the uniform case where all caches serve an equal number of users. We here show for the first time that allowing an optimized memory allocation across the caches as a function of the number of users served per cache, provides for the aforementioned DoF. A subsequent index-coding based converse proves that this performance can be close to optimal for bounded values of t.

The work considers the K-user cache-aided sharedlink broadcast channel where each user has access to exactly z caches of normalized size γ, and where each cache assists exactly z users. For this setting, for two opposing memory regimes, we propose novel caching and coded delivery schemes which maximize the local caching gain, and achieve a coding gain larger than 1+Kγ (users served at a time) despite the fact that the total cache redundancy remains Kγ irrespective of z. Interestingly, when z = (κ-1)/(Kγ), the derived optimal coding gain is Kγz + 1, matching the performance of a hypothetical scenario where each user has its own dedicated cache of size zγ.

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 longstanding subpacketization bottleneck of coded caching by reducing the required subpacketization to approximately its Lth 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 multiantenna 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 , while if extra transmitting antennas were added, the subpacketization was previously known to match or exceed S1. Now for L=5, our scheme offers the theoretical (unconstrained) cumulative DoF dI = L+G = 5 +10 = 15, with subpacketization SL=\binomK/LG/L=\binom100/510/5=190. The scheme's performance, given, subpacketization sL=\binomK/LG/L, is within a factor of 2 from the optimal linear sum-DoF. The gains stemming from this work come by a virtual decomposition of the fully connected cache-aided channel into parallel ones, which significantly reduces the required subpacketization

In the context of the K-user MISO broadcast channel with cache-aided receivers, recent multi-antenna coded-caching techniques have sought to complement the traditional multiplexing gains associated to multiple (L) antennas, with the (potentially unbounded) caching gains (G) associated to coded caching. To date, all known existing efforts to combine the two gains, either resulted in a maximum known DoF L + G that required though CSIT on all (L + G) users served at a time (i.e., that induced potentially unbounded CSIT costs that matched the DoF gains), or resulted in a much compromised DoF where multiplexing gains came at the expense of bounded or vanishing caching gains. We present here a new multi-antenna coded caching algorithm that introduces a new XOR generation structure which completely untangles caching gains from CSIT, delivering the desired sum-DoF of L + G but with a much reduced CSIT cost of only L channel vectors at a time (L × L CSIT matrix). This means that for the first time in multi-antenna coded caching, one can achieve full multiplexing gains and unbounded caching gains, at the mere CSIT cost associated to achieving the multiplexing gains. In the end, the result solidifies the role of coded caching as a method for reducing feedback requirements in multi-antenna environments.

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 internode 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 techniques in the context of MapReduce 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 necessited 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 mapping tasks and then employing a here-proposed novel D2D coded caching algorithm. In this context, the new approach here manages to achieve a virtual decomposition of the fully connected D2D setting into parallel ones, which significantly reduces the required subpacketization.

The work identifies the performance limits of the multiple-input single-output broadcast channel where cache-aided users coincide with users that do not have caches. 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. This performance is shown to be within a factor of at most 3 from the optimal, under the assumption of linear one-shot schemes. An interesting outcome is the following: starting from a single-stream centralized coded caching setting with normalized cache size γ, then every addition of an extra transmit antenna allows for the addition of approximately 1/γ extra cache-less users, at no added delay costs. For example, starting from a single-stream coded caching setting with γ = 1/100, every addition of a transmit antenna, allows for serving approximately an additional 100 more cache-less users, without any increase in the overall delay. Finally the work reveals the role of multiple antennas in removing the penalties typically associated to cache-size unevenness, as it shows that the performance in the presence of both cache-less and cache-aided users, matches the optimal (under uncoded cache placement) performance of the corresponding symmetric case where the same cumulative cache volume is split evenly across all users.

In the context of caching in heterogeneous networks, the work explores the setting where a multi-antenna transmitter (No antennas), broadcasts to K receiving users, each assisted by one of Λ ≤ K helper nodes serving as limited-sized caches. Our aim is to identify the limits of coded caching when there are fewer caches than users (Λ0, adding a single degree of cache-redundancy yields a caching-gain increase equal to No, and similarly, adding antennas has a multiplicative DoF impact where for example introducing a second transmit antenna can double the DoF.

In the context of coded caching in the K-user broadcast channel, 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 Lth 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 manages for the first time to virtually decompose the fully connected cache-aided channel into L parallel channels. The scheme is practical; it works for all the values of K and L and all cache sizes, and its 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 S1= (K;G) = (100;10) > 1013, while if extra transmitting antennas were added, the subpacketization was previously known to match or exceed S1. Now for L = 5, our scheme offers the theoretical (unconstrained) cumulative DoF dL= L + G = 5 + 10 = 15, with subpacketization SL= (K/L;G/L) = (100/5;10/5) = 190. The work extends to the multi-server and cache-aided IC settings, while the scheme's performance, given subpacketization SL= (K/L;G/L), is within a factor of 2 from the optimal linear sum-DoF.

International audience

This work explores cache-aided interference management in the absence of channel state information at the transmitters (CSIT), focusing on the setting with K transmitter/receiver pairs endowed with caches, where each receiver k is connected to transmitter k via a direct link with normalized capacity 1, and to any other transmitter via a cross link with normalized capacity τ ≤ 1. In this setting, we explore how a combination of pre-caching at transmitters and receivers, together with interference enhancement techniques, can a) partially counter the lack of CSIT, and b) render the network self-sufficient, in the sense that the transmitters need not receive additional data after pre-caching. Toward this we present new schemes that blindly harness topology and transmitter-and-receiver caching, to create separate streams, each serving many receivers at a time. Key to the approach here is a combination of rate-splitting, interference enhancement and coded caching.

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 Tgwhere 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 τ, 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 T = 1.

Coded caching is a communications technique that has elevated the preemptive use of memory (caching) into a powerful ingredient in general communications networks, promising to change the way networking and PHY-based communications are conducted. At the same time though - because this approach is heavily dependent on cooperation between the content provider (CP), and a centralized powerful transmitter of information (ISP), and because it is heavily dependent on users caching a variety of content that is not their own - raises privacy concerns which have the potential to compromise the applicability of coded caching. What we are showing in this early work here, is that in fact coded caching carries a distinct set of salient features that in fact boost privacy. We present a step-by-step privacy-aware content-delivery protocol that utilizes caching and which - at a small cost in performance - can safeguard against unauthorized matching of users to their requests, as well as against unauthorized knowledge of the popularity statistics of files; both crucial privacy issues in different scenarios such as video on demand. These properties include multicasting-only transmissions for continuous obfuscation of the true destination of content, an almost seamless addition of phantom users that can skew the true popularity distribution, popularity-agnostic caches, cache-agnostic ISP, and an overall minimization of data traffic between CP and ISP, and between ISP and users.

Building on the recent coded-caching breakthrough by Maddah-Ali and Niesen, the work here considers the $K$ -user cache-aided wireless multi-antenna symmetric broadcast channel with random fading and imperfect feedback, and analyzes the throughput performance as a function of feedback statistics and cache size. In this setting, this paper identifies the optimal cache-aided degrees-of-freedom (DoF) within a factor of 4, by identifying near-optimal schemes that exploit a new synergy between coded caching and delayed CSIT, as well as by exploiting the unexplored interplay between caching and feedback-quality. The DoF expressions reveal an initial gain due to current CSIT, and an additional gain due to coded caching, which is exponential in the sense that any linear decrease in the required DoF performance, allows for an exponential reduction in the required cache size. In the end, this paper reveals three new aspects of caching: a synergy between memory and delayed feedback, a tradeoff between memory and current CSIT, and a powerful ability to provide cache-aided feedback savings.

This work1derives 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 channel estimation error scales in P-αfor α ∈ [0, 1]. The optimal sum DoF takes the simple form (1 - α)K/HK+ αK where HK =△ Σk=1K1/k. This optimal performance is the result of a novel scheme which deviates from existing efforts as it digitally combines interference, decodes symbols of any order in the MAT alignment [1], and utilizes a hierarchical quantizer whose output is distributed across rounds in a way that minimizes unwanted interference. These jointly deliver, for the first time, the elusive DoF-optimal combining of MAT and ZF.

Recent research has explored the possibility of extracting ancillary information from primary biometric traits viz., face, fingerprints, hand geometry, and iris. This ancillary information includes personal attributes, such as gender, age, ethnicity, hair color, height, weight, and so on. Such attributes are known as soft biometrics and have applications in surveillance and indexing biometric databases. These attributes can be used in a fusion framework to improve the matching accuracy of a primary biometric system (e.g., fusing face with gender information), or can be used to generate qualitative descriptions of an individual (e.g., young Asian female with dark eyes and brown hair). The latter is particularly useful in bridging the semantic gap between human and machine descriptions of the biometric data. In this paper, we provide an overview of soft biometrics and discuss some of the techniques that have been proposed to extract them from the image and the video data. We also introduce a taxonomy for organizing and classifying soft biometric attributes, and enumerate the strengths and limitations of these attributes in the context of an operational biometric system. Finally, we discuss open research problems in this field. This survey is intended for researchers and practitioners in the field of biometrics.

In the setting of the two-user single-input single-output X channel, recent works have explored the degrees-offreedom (DoF) limits in the presence of perfect channel state information at the transmitter (CSIT), as well as in the presence of perfect-quality delayed CSIT. Our work shows that the same DoF-optimal performance - previously associated to perfect-quality current CSIT - can in fact be achieved with current CSIT that is of imperfect quality. The work also shows that the DoF performance previously associated to perfect-quality delayed CSIT, can in fact be achieved in the presence of imperfect-quality delayed CSIT. These follow from the presented sum-DoF lower bound that bridges the gap - as a function of the quality of delayed CSIT - between the cases of having no feedback and having delayed feedback, and then another bound that bridges the DoF gap - as a function of the quality of current CSIT - between delayed and perfect current CSIT. The bounds are based on novel precoding schemes that are presented here and which employ imperfect-quality current and/or delayed feedback to align interference in space and in time.

In many wireless networks, link strengths are affected by many topological factors, such as different distances, shadowing, and intercell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects is still a novel approach, that has been recently fueled by strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. This paper 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 versus weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter [alternating channel state information at the transmitter (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 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.

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.

The work considers the two-user MISO broadcast channel with a 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 with delays, that may not immediately convey perfect CSIT, and focusing on the block fading scenario, we consider a gradual accumulation of feedback bits that results in a progressively increasing CSIT quality as time progresses across the coherence period (T channel uses - current CSIT), or at any time after (delayed CSIT). Specifically, for any set {αt}Tt=1of feedback quality exponents describing the high-SNR rates-of-decay of the mean square error of the current CSIT estimates at time t ≤ T (01≤ · · · ≤ (αT≤ 1), given an average α = ΣTt=1αt/T, and given perfect delayed CSIT (received at any time t > T), the work here derives the optimal DoF region to be the polygon with corner points {(0,0),(0,1),(α,1),(2+α/3, 2+α/3),(1,α),(1,0)}. Aiming to now reduce the overall number of feedback bits, we also prove that the above optimal region holds even with imperfect delayed CSIT for any (delayed-CSIT) quality exponent β ≥ 1+2α/3. The results are supported by novel multi-phase precoding schemes that utilize gradually improving CSIT. The approach here incorporates different settings such as the delayed CSIT setting of Maddah-Ali and Tse (β = 1, αt= 0, ∀t ≤ T), the imperfect current CSIT setting of Yang et al. and of Gou and Jafar (β = 1, α1= · · · = αT> 0), and the not-so-delayed CSIT setting of Lee and Heath (β = 1, α1= · · · = αT= 0 for some τ<;T).

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 M ×1 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.

Recent work in [1]-[3] quantified, in the form of a complexity exponent, the computational resources required for ML and lattice sphere decoding to achieve a certain diversity-multiplexing performance. For a specific family of layered lattice designs, and a specific set of decoding orderings, this complexity was shown to be an exponential function in the number of codeword bits, and was shown to meet a universal upper bound on complexity exponents. The same results raised the question of whether complexity reductions away from the universal upper bound are feasible, for example, with a proper choice of decoder (ML vs lattice), or with a proper choice of lattice codes and decoding ordering policies. The current work addresses this question by first showing that for almost any full-rate DMT optimal lattice code, there exists no decoding ordering policy that can reduce the complexity exponent of ML or lattice based sphere decoding away from the universal upper bound, i.e., that a randomly picked lattice code (randomly and uniformly drawn from an ensemble of DMT optimal lattice designs) will almost surely be such that no decoding ordering policy can provide exponential complexity reductions away from the universal upper bound. As a byproduct of this, the current work proves the fact that ML and (MMSE-preprocessed) lattice decoding share the same complexity exponent for a very broad setting, which now includes almost any DMT optimal code (again randomly drawn) and all decoding order policies. Under a basic richness of codes assumption, this is in fact further extended to hold, with probability one, over all full-rate codes. Under the same assumption, the result allows for a meaningful rate-reliability-complexity tradeoff that holds, almost surely in the random choice of the full-rate lattice design, and which holds irrespective of the decoding ordering policy. This tradeoff can be used to, for example, describe the optimal achievable diversity gain of ML or lattice sphere decoding in the presence of limited computational resources.

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. This paper 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. This paper 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 nonblock 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.

Maddah-Ali and Tse have recently shown that delayed transmitter channel state information (CSIT) can still be useful in increasing the degrees-of-freedom (DoF) over the MIMO broadcast channel. This was achieved by constructing a scheme that, in the presence of two transmit antennas, of two single-antenna receivers, and of CSIT that is delayed by one coherence time, manages to provide each user with 2/3 DoF, improving upon the 1/2 DoF corresponding to no CSIT. This same scheme though, as well as all subsequent schemes pertinent schemes, achieve DoF gains by suppressing the inherent diversity of the broadcast parallel channel. The current work proposes a novel broadcast scheme which, over the above described setting of the delayed CSIT broadcast channel, employs a form of interference alignment to achieve both full DoF as well as full diversity.

The work analyzes the computational-complexity savings that a single bit of feedback can provide in the computationally intense setting of non-ergodic MIMO communications. Specifically we derive upper bounds on the feedback-aided complexity exponent required for the broad families of ML-based and lattice based decoders to achieve the optimal diversity-multiplexing behavior. The bounds reveal a complexity that is reduced from being exponential in the number of codeword bits, to being at most exponential in the rate. Finally the derived savings are met by practically constructed ARQ schemes, as well as simple lattice designs, decoders, and computation-halting policies.

In the setting of quasi-static multiple-input multiple-output channels, we consider the high signal-to-noise ratio (SNR) asymptotic complexity required by the sphere decoding (SD) algorithm for decoding a large class of full-rate linear space-time codes. With SD complexity having random fluctuations induced by the random channel, noise, and codeword realizations, the introduced SD complexity exponent manages to concisely describe the computational reserves required by the SD algorithm to achieve arbitrarily close to optimal decoding performance. Bounds and exact expressions for the SD complexity exponent are obtained for the decoding of large families of codes with arbitrary performance characteristics. For the particular example of decoding the recently introduced threaded cyclic-division-algebra-based codes—the only currently known explicit designs that are uniformly optimal with respect to the diversity multiplexing tradeoff—the SD complexity exponent is shown to take a particularly concise form as a non-monotonic function of the multiplexing gain. To date, the SD complexity exponent also describes the minimum known complexity of any decoder that can provably achieve a gap to maximum likelihood performance that vanishes in the high SNR limit.

Nine new two-dimensional Optical Orthogonal Codes (2-D OOCs) are presented here, all sharing the common feature of a code size that is much larger in relation to the number of time slots than those of constructions appearing previously in the literature. Each of these constructions is either optimal or asymptotically optimal with respect to either the original Johnson bound or else a nonbinary version of the Johnson bound introduced in this paper. The first five codes are constructed using polynomials over finite fields—the first construction is optimal while the remaining four are asymptotically optimal. The next two codes are constructed using rational functions in place of polynomials and these are asymptotically optimal. The last two codes, also asymptotically optimal, are constructed by composing two of the above codes with a constant weight binary code. Also presented is a three-dimensional Optical Orthogonal Code (3-D OOC) that exploits the polarization dimension. Finally, phase-encoded optical CDMA is considered and construction of two efficient codes are provided.

This study identifies the first lattice decoding solution that achieves, in the general outage-limited multiple-input multiple-output (MIMO) setting and in the high-rate and high-signal-to-noise ratio limit, both a vanishing gap to the error performance of the exact solution of regularized lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits and in the rate. The proposed solution employs Lenstra-Lenstra-Lovász-based lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. These performance and complexity guarantees hold for most MIMO scenarios, most fading statistics, all channel dimensions, and all full-rate lattice codes. In sharp contrast to the aforementioned very manageable complexity, the complexity of other standard preprocessed lattice decoding solutions is revealed here to be extremely high. Specifically, this study has quantified the complexity of regularized lattice (sphere) decoding and has proved that the computational resources required by this decoder to achieve a good rate-reliability performance are exponential in the lattice dimensionality and in the number of codeword bits, and it in fact matches, in common scenarios, the complexity of ML-based sphere decoders. Through this sharp contrast, this study was able to, for the first time, rigorously demonstrate and quantify the pivotal role of LR as a special complexity reducing ingredient.

In the context of multiuser relay-aided multi-way communications, we identify and meet the optimal degrees of freedom (DOF) for different multiuser uplink-downlink settings of practical importance. Under the imposed constraint of using simple linear techniques, the proposed solutions draw from interference-neutralization (IN) methods which linearly manipulate signals in time and space, and manage to reduce the effect of multiuser interference and of the half-duplex constraint. Focus is placed on asymmetric settings where the connectivity, size and rate of the uplink and downlink groups may vary.

We consider the complexity of the sphere decoding (SD) algorithm when decoding a class of full rate space-time block codes that are optimal, over the quasi-static MIMO channel, with respect to the diversity-multiplexing tradeoff (DMT). Towards this we introduce the SD complexity exponent which represents the high signal-to-noise ratio (SNR) exponent of the tightest run-time complexity constraints that can be imposed on the SD algorithm while maintaining arbitrarily close to maximum likelihood (ML) performance. Similar to the DMT exposition, our approach naturally captures the dependence of the SD algorithm's computational complexity on the codeword density, code size and channel randomness, and provides simple closed form solutions in terms of the system dimensions and the multiplexing gain.

The work establishes fundamental limits between rate, reliability and computational complexity, for the general setting of outage-limited MIMO communications. In the high-SNR regime, the limits are optimized over all encoders, all decoders, and all complexity regulating policies. The work then proceeds to explicitly identify encoder-decoder designs and policies, that meet this optimal tradeoff. In practice, the limits aim to meaningfully quantify different pertinent and interrelated measures, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal goodput per flop. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders.

The work establishes the asymptotic rate of decay for the probability of node isolation in bounded wireless sensor networks, in the high density regime. In this regime, the exposition reveals the role of the most isolated neighborhoods of the bounding region in exponentially increasing the average probability of isolation. The problem is treated for a large family of random spatial distributions of nodes, random shapes of node coverage areas, and random topography of the network's bounding region. Different examples are presented to insightfully describe the detrimental effect of boundedness in network isolation. Finally we address different aspects relating to extremely isolating bounding regions, and densities that vary exponentially in time.

This work introduces the novel idea of using a bag of facial soft biometrics for person verification and identification. The novel tool inherits the non-intrusiveness and computational efficiency of soft biometrics, which allow for fast and enrolment-free biometric analysis, even in the absence of consent and cooperation of the surveillance subject. In conjunction with the proposed system design and detection algorithms, we also proceed to shed some light on the statistical properties of different parameters that are pertinent to the proposed system, as well as provide insight on general design aspects in soft-biometric systems, and different aspects regarding efficient resource allocation.

This paper identifies the first general, explicit, and nonrandom MIMO encoder-decoder structures that guarantee optimality with respect to the diversity-multiplexing tradeoff (DMT), without employing a computationally expensive maximum-likelihood (ML) receiver. Specifically, the work establishes the DMT optimality of a class of regularized lattice decoders, and more importantly the DMT optimality of their lattice-reduction (LR)-aided linear counterparts. The results hold for all channel statistics, for all channel dimensions, and most interestingly, irrespective of the particular lattice-code applied. As a special case, it is established that the LLL-based LR-aided linear implementation of the MMSE-GDFE lattice decoder facilitates DMT optimal decoding of any lattice code at a worst-case complexity that grows at most linearly in the data rate. This represents a fundamental reduction in the decoding complexity when compared to ML decoding whose complexity is generally exponential in the rate. The results' generality lends them applicable to a plethora of pertinent communication scenarios such as quasi-static MIMO, MIMO-OFDM, ISI, cooperative-relaying, and MIMO-ARQ channels, in all of which the DMT optimality of the LR-aided linear decoder is guaranteed. The adopted approach yields insight, and motivates further study, into joint transceiver designs with an improved SNR gap to ML decoding.

Explicit codes are constructed that achieve the diversity-multiplexing gain tradeoff (DMT) of the cooperative-relay channel under the dynamic decode-and-forward protocol for any network size and for all numbers of transmit and receive antennas at the relays. Along the way, we prove that space-time codes previously constructed in the literature for the block-fading and parallel channels are approximately universal, i.e., they achieve the DMT for any fading distribution. It is shown how approximate universality of these codes leads to the first DMT-optimum code construction for the general, MIMO-OFDM channel.

Currently for the nTtimes nRMIMO channel, any explicitly constructed space-time (ST) designs that achieve optimality with respect to the diversity multiplexing tradeoff (DMT) are known to do so only when decoded using maximum likelihood (ML) decoding, which may incur prohibitive decoding complexity. In this paper we prove that MMSE regularized lattice decoding, as well as the computationally efficient lattice reduction (LR) aided MMSE decoder, allows for efficient and DMT optimal decoding of any approximately universal latticebased code. The result identifies for the first time an explicitly constructed encoder and a computationally efficient decoder that achieve DMT optimality for all multiplexing gains and all channel dimensions. The results hold irrespective of the fading statistics.

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), nonorthogonal and orthogonal selection decode-and-forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time (ST) code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay.

This work analyzes the high-SNR asymptotic error performance of outage-limited communications with fading, where the number of bits that arrive at the transmitter during any timeslot is random but the delivery of bits at the receiver must adhere to a strict delay limitation. Specifically, bit errors are caused by erroneous decoding at the receiver or violation of the strict delay constraint. Under certain scaling of the statistics of the bit-arrival process with SNR, this paper shows that the optimal decay behavior of the asymptotic total probability of bit error depends on how fast the burstiness of the source scales down with SNR. If the source burstiness scales down too slowly, the total probability of error is asymptotically dominated by delay-violation events. On the other hand, if the source burstiness scales down too quickly, the total probability of error is asymptotically dominated by channel-error events. However, at the proper scaling, where the burstiness scales linearly with${{ 1}\over { \sqrt {\log {\rm SNR} }}}$and at the optimal coding duration and transmission rate, the occurrences of channel errors and delay-violation errors are asymptotically balanced. In this latter case, the optimal exponent of the total probability of error reveals a tradeoff that addresses the question of how much of the allowable time and rate should be used for gaining reliability over the channel and how much for accommodating the burstiness with delay constraints.

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with$n_{t}$transmit and$n_{r}$receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity–multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an$L$-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number$L$of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity–multiplexing–delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback.

This work investigates the asymptotic error performance of outage-limited communications in cooperative wireless relay networks, with fading that is quasi-static, with an information-arrival process that is stochastic and bursty, and with bits that have a strictly limited lifespan. Employing large- deviation techniques, we analyze the probability of bit error where such errors are due to both erroneous decoding as well as due to delay violation. We derive a tradeoff between, on one hand, the optimal negative SNR exponent of the total probability of error, and on the other hand, the ratio of the average bit- arrival rate to the ergodic capacity of the channel. This is for the case of the orthogonal amplify-and-forward protocol, constant system loading, many flows and asymptotically high values of SNR. The tradeoff holds for any delay limitation. As a practical consequence, the tradeoff tells us how to better balance the effects of channel atypicality (outage) and burstiness atypicality, by proper choice of transmission rate and by optimizing the cooperative cluster size, i.e., limiting the cooperation to a specific subset of the cooperative users.

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), non-orthogonal and orthogonal selection decode-and- forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay. Included in our results is the perhaps surprising finding that the OAF and NAF protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time occupied by the broadcast phase is allowed to vary with multiplexing gain. In the two-relay case, the variable-NSDF protocol is shown to improve on the DMT of the best previously-known static protocol for higher values of multiplexing gain. Our results also establish that the fixed-NSDF protocol has a better DMT than the NAF protocol for any number of relays.

This paper considers an orthogonal amplify-and-forward (OAF) protocol for cooperative relay communication over Rayleigh-fading channels in which the intermediate relays are permitted to linearly transform the received signal and where the source and relays transmit for equal time durations. The diversity-multiplexing gain (D-MG) tradeoff of the equivalent space-time channel associated to this protocol is determined and a cyclic-division-algebra-based D-MG optimal code constructed. The transmission or signaling alphabet of this code is the union of the QAM constellation and a rotated version of QAM. The size of this signaling alphabet is small in comparison with prior D-MG optimal constructions in the literature and is independent of the number of participating nodes in the network.

In a recent paper, perfect$(n \times n)$space–time codes were introduced as the class of linear dispersion space–time (ST) codes having full rate, nonvanishing determinant, a signal constellation isomorphic to either the rectangular or hexagonal lattices in$2n^2$dimensions, and uniform average transmitted energy per antenna. Consequence of these conditions include optimality of perfect codes with respect to the Zheng–Tse diversity–multiplexing gain tradeoff (DMT), as well as excellent low signal-to-noise ratio (SNR) performance. Yet perfect space–time codes have been constructed only for two, three, four, and six transmit antennas.

It has been shown by Li and Xia that there exist cooperative diversity schemes that can provide for diversity gains in wireless networks even without symbol synchronicity between cooperative network users. These asynchronicity-tolerant schemes were based on distributed space-time codes which maintained their full-rank property for specific asynchronicity cases and specific numbers of users. By expanding the signaling set, we provide constructions of schemes that maintain near-optimal error performance, given certain cooperation strategies and given synchronicity, and which are asynchronicity-tolerant, with probability one, for any asynchronicity profile and for all numbers of network users. By relating the problem of asynchronicity to the maximum degrees of freedom provided by a cooperative-diversity scheme, we are further able to provide cooperative diversity methods that are empirically shown to translate asynchronicity to reduction of the probability of error.

In this work, we construct a unified family of cooperative diversity coding schemes for implementing the orthogonal amplify-and-forward and the orthogonal selection-decode-and-forward strategies in cooperative wireless networks. We show that, as the number of users increases, these schemes meet the corresponding optimal high-SNR outage region, and do so with minimal order of signaling complexity. This is an improvement over all outage-optimal schemes which impose exponential increases in signaling complexity for every new network user. Our schemes, which are based on commutative algebras of normal matrices, satisfy the outage-related information theoretic criteria, the duplex-related coding criteria, and maintain reduced signaling, encoding and decoding complexities

A recent result of Zheng and Tse states that over a quasi-static channel, there exists a fundamental tradeoff, referred to as the diversity–multiplexing gain (D-MG) tradeoff, between the spatial multiplexing gain and the diversity gain that can be simultaneously achieved by a space–time (ST) code. This tradeoff is precisely known in the case of independent and identically distributed (i.i.d.) Rayleigh fading, for$T geq n_t+n_r-1$where$T$is the number of time slots over which coding takes place and$n_t,n_r$are the number of transmit and receive antennas, respectively. For$T ≪ n_t+n_r-1$, only upper and lower bounds on the D-MG tradeoff are available. In this paper, we present a complete solution to the problem of explicitly constructing D-MG optimal ST codes, i.e., codes that achieve the D-MG tradeoff for any number of receive antennas. We do this by showing that for the square minimum-delay case when$T=n_t=n$, cyclic-division-algebra (CDA)-based ST codes having the nonvanishing determinant property are D-MG optimal. While constructions of such codes were previously known for restricted values of$n$, we provide here a construction for such codes that is valid for all$n$. For the rectangular,$T ≫ n_t$case, we present two general techniques for building D-MG-optimal rectangular ST codes from their square counterparts. A byproduct of our results establishes that the D-MG tradeoff for all$Tgeq n_t$is the same as that previously known to hold for$T geq n_t + n_r -1$.

In the recent landmark paper of Zheng and Tse it is shown for the quasi-static, Rayleigh-fading MIMO channel with n/sub t/ transmit and n/sub r/ receive antennas, that there exists a fundamental tradeoff between diversity gain and multiplexing gain, referred to as the diversity-multiplexing gain (D-MG) tradeoff. This paper presents the first explicit construction of space-time (ST) codes for an arbitrary number of transmit and/or receive antennas that achieve the D-MG tradeoff. It is shown here that ST codes constructed from cyclic-division-algebras (CDA) and satisfying a certain non-vanishing determinant (NVD) property, are optimal under the D-MG tradeoff for any n/sub t/,n/sub r/. Furthermore, this optimality is achieved with minimum possible value of the delay or block-length parameter T = n/sub t/. CDA-based ST codes with NVD have previously been constructed for restricted values of n/sub t/. A unified construction of D-MG optimal CDA-based ST codes with NVD is given here, for any number n/sub t/ of transmit antennas. The CDA-based constructions are also extended to provide D-MG optimal codes for all T /spl ges/ n/sub t/, again for any number nt of transmit antennas. This extension thus presents rectangular D-MG optimal space-time codes that achieve the D-MG tradeoff. Taken together, the above constructions also extend the region of T for which the D-MG tradeoff is precisely known from T /spl ges/ n/sub t/ + n/sub r/ - 1 to T /spl ges/ n/sub t/.

For the quasi-static, Rayleigh-fading MIMO channel with nttransmit and nrreceive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Explicit constructions for D-MG optimal ST codes are now available. In a subsequent paper, El Gamal, Caire and Damen considered signaling across the quasi-static ST channel using an L-round ARQ protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information (ACK or NACK) per use of the feedback channel. They showed that given a fixed number of ARQ rounds L, there is a tradeoff between diversity and multiplexing gains under which the optimum diversity gain of the ARQ channel transmitting R = r log(SNR) bits per channel use, is that of the quasi-static channel without feedback investigated by Zheng and Tse, transmitting at (1/L)th the information rate. This tradeoff, which now is a function of the number L of ARQ rounds, is termed the diversity-multiplexing gain-delay (DMD) tradeoff. In the current paper, a sufficient condition under which a ST code will achieve the DMD tradeoff is presented for the case nrges nt. The cyclic-division-algebra-based constructions of DMG optimal ST codes by Elia et. al. are then modified to yield codes which meet this sufficient criterion and are thereby DMD-optimal. This modification requires that either nt|L or L|nt