BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Petros Elia

Petros Elia appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITComputational Complexityeess.SPmath.RAmath.STStatistics Theory

Catalog footprint

What is connected

35works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

35 published item(s)

preprint2026arXiv

Caching Yields up to 5x Spectral Efficiency in Multi-Beam Satellite Communications

This paper examines the integration of vector coded caching (VCC) into multi-beam satellite communications (SATCOM) systems and demonstrates that even limited receiver-side caching can substantially enhance spectral efficiency. By leveraging cached content to suppress interference, VCC enables the concurrent transmission of multiple precoded signal vectors that would otherwise require separate transmission resources. This leads to a multiplicative improvement in resource utilization in SATCOM. To characterize this performance, we model the satellite-to-ground channel using Rician-shadowed fading and after incorporating practical considerations such as matched-filter precoding, channel state information (CSI) acquisition overhead as well as CSI imperfections at the transmitter, we here derive closed-form expressions for the average sum rate and spectral efficiency gain of VCC in SATCOM. Our analysis, tightly validated through numerical simulations, reveals that VCC can yield spectral efficiency gains of 300% to 550% over traditional multi-user MISO SATCOM with the same resources. These gains -- which have nothing to do with multicasting, prefetching gains nor file popularity -- highlight VCC as a pure physical-layer solution for future high-throughput SATCOM systems, significantly narrowing the performance gap between satellite and wired networks.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Fundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Universal and Asymptotically Optimal Data and Task Allocation in Distributed Computing

We study the joint minimization of communication and computation costs in distributed computing, where a master node coordinates $N$ workers to evaluate a function over a library of $n$ files. Assuming that the function is decomposed into an arbitrary subfunction set $\mathbf{X}$, with each subfunction depending on $d$ input files, renders our distributed computing problem into a $d$-uniform hypergraph edge partitioning problem wherein the edge set (subfunction set), defined by $d$-wise dependencies between vertices (files) must be partitioned across $N$ disjoint groups (workers). The aim is to design a file and subfunction allocation, corresponding to a partition of $\mathbf{X}$, that minimizes the communication cost $π_{\mathbf{X}}$, representing the maximum number of distinct files per server, while also minimizing the computation cost $δ_{\mathbf{X}}$ corresponding to a maximal worker subfunction load. For a broad range of parameters, we propose a deterministic allocation solution, the \emph{Interweaved-Cliques (IC) design}, whose information-theoretic-inspired interweaved clique structure simultaneously achieves order-optimal communication and computation costs, for a large class of decompositions $\mathbf{X}$. This optimality is derived from our achievability and converse bounds, which reveal -- under reasonable assumptions on the density of $\mathbf{X}$ -- that the optimal scaling of the communication cost takes the form $n/N^{1/d}$, revealing that our design achieves the order-optimal \textit{partitioning gain} that scales as $N^{1/d}$, while also achieving an order-optimal computation cost. Interestingly, this order optimality is achieved in a deterministic manner, and very importantly, it is achieved blindly from $\mathbf{X}$, therefore enabling multiple desired functions to be computed without reshuffling files.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Multi-User Distributed Computing Via Compressed Sensing

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 $γ\leq \frac{K}{N}$ that a generally intractable $\ell_0$-minimization would give. To bypass the intractability of such optimal scheme, we show that if these optimal schemes enjoy $γ\leq - r\frac{K}{N}W^{-1}_{-1}(- \frac{2K}{e N r} )$ (where $W_{-1}(\cdot)$ is the Lambert function and $r$ calibrates the communication between servers and users), then they can actually be derived using a tractable Basis Pursuit $\ell_1$-minimization. This newly-revealed connection between distributed computation and compressed sensing opens up the possibility of designing practical distributed computing algorithms by employing tools and methods from compressed sensing.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Coded Caching Does Not Generally Benefit From Selfish Caching

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

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Coded Caching in Networks with Heterogeneous User Activity

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

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-Access Distributed Computing

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

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-User Linearly-Separable Distributed Computing

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Exact Load-Memory Tradeoff of Multi-Access Coded Caching With Combinatorial Topology

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Vector Coded Caching Multiplicatively Boosts the Throughput of Realistic Downlink Systems

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

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fundamental Limits of Stochastic Shared Caches Networks

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 $Θ\left( \frac{\log Λ}{\log \log Λ} \right)$ at $K=Θ\left(Λ\right)$, and that this scaling vanishes when $K=Ω\left(Λ\log Λ\right)$. To alleviate this adverse effect of cache-load imbalance, we consider various load balancing methods, and show that employing proximity-bounded load balancing with an ability to choose from $h$ neighboring caches, the aforementioned scaling reduces to $Θ\left(\frac{\log(Λ/ h)}{ \log \log(Λ/ h)} \right)$, while when the proximity constraint is removed, the scaling is of a much slower order $Θ\left( \log \log Λ\right)$. The above analysis is extensively validated numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Rate-Memory Trade-Off for the Cache-Aided MISO Broadcast Channel with Hybrid CSIT

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

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Wireless Coded Caching Can Overcome the Worst-User Bottleneck by Exploiting Finite File Sizes

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Full Coded Caching Gains for Cache-less Users

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 $γ$, 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 \emph{multiplicative} factor of up to $Γ_{2}+L$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fundamental Limits of Wireless Caching under Uneven-Capacity Channels

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Resolving the Feedback Bottleneck of Multi-Antenna Coded Caching

Multi-antenna cache-aided wireless networks have been known to suffer from a severe feedback bottleneck, where achieving the maximal Degrees-of-Freedom (DoF) performance required feedback from all served users. These costs matched the caching gains and thus scaled with the number of users. In the context of the $L$-antenna MISO broadcast channel with $K$ receivers having normalized cache size $γ$, we pair a fundamentally novel algorithm together with a new information-theoretic converse, and identify the optimal tradeoff between feedback costs and DoF performance, by showing that having CSIT from only $C<L$ served users implies an optimal one-shot linear DoF of $C+Kγ$. As a side consequence of this, we also now understand that the well known DoF performance $L+Kγ$ is in fact exactly optimal. In practice, the above means that we are now 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Feedback-Aided Coded Caching for the MISO BC with Small Caches

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

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fundamental Limits of Cache-Aided Wireless BC: Interplay of Coded-Caching and CSIT Feedback

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

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal DoF of the K-User Broadcast Channel with Delayed and Imperfect Current CSIT

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

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Synergistic Gains of Coded Caching and Delayed Feedback

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

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Wireless Coded Caching: A Topological Perspective

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 $τ<1$, we identify --- as a function of the cache size and $τ$ --- the optimal throughput performance, within a factor of at most 8. The transmission scheme that achieves this performance, employs a simple form of interference enhancement, and exploits the property that weak links attenuate interference, thus allowing for multicasting rates to remain high even when involving weak users. This approach ameliorates the negative effects of uneven topology in multicasting, now allowing all users to achieve the optimal performance associated to $τ=1$, even if $τ$ is approximately as low as $τ\geq 1-(1-w)^g$ where $g$ is the coded-caching gain, and where $w$ is the fraction of users that are weak. This leads to the interesting conclusion that for coded multicasting, the weak users need not bring down the performance of all users, but on the contrary to a certain extent, the strong users can lift the performance of the weak users without any penalties on their own performance. Furthermore for smaller ranges of $τ$, 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 $τ= 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Performance-Complexity Analysis for MAC ML-based Decoding with User Selection

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

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Vector Broadcast Channel with Alternating CSIT: A Topological Perspective

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Fundamental Feedback-vs-Performance Tradeoff over the MISO-BC with Imperfect and Delayed CSIT

This work considers the multiuser multiple-input single-output (MISO) broadcast channel (BC), where a transmitter with M antennas transmits information to K single-antenna users, and where - as expected - the quality and timeliness of channel state information at the transmitter (CSIT) is imperfect. Motivated by the fundamental question of how much feedback is necessary to achieve a certain performance, this work seeks to establish bounds on the tradeoff between degrees-of-freedom (DoF) performance and CSIT feedback quality. Specifically, this work provides a novel DoF region outer bound for the general K-user MISO BC with partial current CSIT, which naturally bridges the gap between the case of having no current CSIT (only delayed CSIT, or no CSIT) and the case with full CSIT. The work then characterizes the minimum CSIT feedback that is necessary for any point of the sum DoF, which is optimal for the case with M >= K, and the case with M=2, K=3.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal DoF Region of the Two-User MISO-BC with General Alternating CSIT

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

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Symmetric Two-User MIMO BC and IC with Evolving Feedback

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

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Toward the Performance vs. Feedback Tradeoff for the Two-User MISO Broadcast Channel

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

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Degrees-of-Freedom Region of the MISO Broadcast Channel with General Mixed-CSIT

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

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Imperfect Delayed CSIT can be as Useful as Perfect Delayed CSIT: DoF Analysis and Constructions for the BC

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

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

MISO Broadcast Channel with Delayed and Evolving CSIT

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

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Achieving a vanishing SNR-gap to exact lattice decoding at a subexponential complexity

The work identifies the first lattice decoding solution that achieves, in the general outage-limited MIMO setting and in the high-rate and high-SNR limit, both a vanishing gap to the error-performance of the (DMT optimal) exact solution of preprocessed lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits. The proposed solution employs lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. These performance and complexity guarantees hold for most MIMO scenarios, all reasonable fading statistics, all channel dimensions and all full-rate lattice codes. In sharp contrast to the above manageable complexity, the complexity of other standard preprocessed lattice decoding solutions is shown here to be extremely high. Specifically the work is first to quantify the complexity of these lattice (sphere) decoding solutions and to prove the surprising result that the complexity required to achieve a certain rate-reliability performance, is 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 solutions. Through this sharp contrast, the work was able to, for the first time, rigorously quantify the pivotal role of lattice reduction as a special complexity reducing ingredient. Finally the work analytically refines transceiver DMT analysis which generally fails to address potentially massive gaps between theory and practice. Instead the adopted vanishing gap condition guarantees that the decoder's error curve is arbitrarily close, given a sufficiently high SNR, to the optimal error curve of exact solutions, which is a much stronger condition than DMT optimality which only guarantees an error gap that is subpolynomial in SNR, and can thus be unbounded and generally unacceptable in practical settings.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sphere decoding complexity exponent for decoding full rate codes over the quasi-static MIMO channel

In the setting of quasi-static multiple-input multiple-output (MIMO) 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 (CDA) based codes -- the only currently known explicit designs that are uniformly optimal with respect to the diversity multiplexing tradeoff (DMT) -- 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 (ML) performance which vanishes in the high SNR limit.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fundamental Rate-Reliability-Complexity Limits in Outage Limited MIMO Communications

The work establishes fundamental limits with respect to rate, reliability and computational complexity, for a 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 measures, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal number of numerical operations (i.e., flops) per bit. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

DMT Optimality of LR-Aided Linear Decoders for a General Class of Channels, Lattice Designs, and System Models

The work identifies the first general, explicit, and non-random 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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

High-SNR Analysis of Outage-Limited Communications with Bursty and Delay-Limited Information

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 time slot 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/sqrt(log 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.

0 citations0 reviewsNo code linkedOpen access