Motivated by emerging decentralized applications, the game of coding framework has been recently introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory. Still, the reward mechanism available in decentralized systems, motivates the adversary to act rationally. While the decoder, as the data collector (DC), has an acceptance/rejection mechanism, followed by an estimation module, the adversary aims to maximize its utility, as an increasing function of (1) the chance of acceptance (to increase the reward), and (2) estimation error. On the other hand, the decoder also adjusts its acceptance rule to maximize its own utility, as (1) an increasing function of the chance of acceptance (to keep the system functional), (2) decreasing function of the estimation error. Prior works within this framework rely on the assumption that the game is complete—that is, both the DC and the adversary are fully aware of each other's utility functions. However, in practice, the decoder is often unaware of the utility of the adversary. To address this limitation, we develop an algorithm enabling the DC to commit to a strategy that achieves within the vicinity of the equilibrium, without knowledge of the adversary's utility function. Our approach builds on an observation that at the equilibrium, the relationship between the probability of acceptance and the mean squared error (MSE) follows a predetermined curve independent of the specific utility functions of the players. By exploiting this invariant relationship, the DC can iteratively refine its strategy based on observable parameters, converging to a near-optimal solution. We provide theoretical guarantees on sample complexity and accuracy of the proposed scheme.

We consider communication over a fast-fading channel with a very short coherence time, where the channel state information can only be obtained by the receiver. The goal is to study the trade-off between the number of bits that the receiver can correctly decode$R$, and the decoding error probability$\epsilon$. We propose a new channel-agnostic coding scheme based on a constellation with infinite size that allows the recovery of$R$bits per channel with an error of$\epsilon$, where the gap between the$R$and$\frac{1}{2} \log$SNR is double logarithmic in$\epsilon$.

Coded computing has demonstrated promising results in addressing straggler resiliency in distributed computing systems. However, most coded computing schemes are designed for exact computation, requiring the number of responding servers to exceed a certain recovery threshold. Additionally, these schemes are tailored to highly structured functions. Recently, new coded computing schemes for general computing functions, where exact computation is replaced with approximate computation, have emerged. In these schemes, the availability of additional results leads to more accurate estimations of the computational tasks. This flexibility introduces new questions that need to be addressed. This paper considers a practically important scenario in the context of general coded computing, where each server may become a straggler with probability$p$, independently of others. We theoretically analyze the approximation error of two existing general coded computing schemes: Berrut Approximate Coded Computing (BACC) and Learning-Theoretic Coded Computing (LeTCC). Under the probabilistic straggler configuration, we demonstrate that the average approximation error for BACC and LeTCC converges to zero at rates of at least$\mathcal{O}\left(\log _{1 / p}^{4}(N) \cdot N^{-2}\right)$and$\mathcal{O}\left(\log _{1 / p}^{3}(N) \cdot N^{-3}\right)$, respectively. This is perhaps surprising, as earlier results do not indicate convergence when the number of stragglers scales with the total number of servers$N$. However, in this case, despite the average number of stragglers being$N p$, the independence of servers in becoming stragglers allows the approximation error to converge to zero. These theoretical results are validated through experiments on various computational tasks, including deep neural networks.

In this paper, we investigate the adversarial robustness of nonparametric regression, a fundamental problem in machine learning, under the setting where an adversary can arbitrarily corrupt a subset of the input data. While the robustness of parametric regression has been extensively studied, its nonparametric counterpart remains largely unexplored. We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space (i.e., it is square integrable up to its second derivative). The contribution of this paper is two-fold: (i) we establish a minimax lower bound on the estimation error, revealing a fundamental limit that no estimator can overcome, and (ii) we show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption. These results imply that if $o(n)$ out of $n$ samples are corrupted, the estimation error of the smoothing spline vanishes as $n \to \infty$. On the other hand, when a constant fraction of the data is corrupted, no estimator can guarantee vanishing estimation error, implying the optimality of the smoothing spline in terms of maximum tolerable number of corrupted samples.

In this paper, we propose ByzSecAgg, an efficient secure aggregation scheme for federated learning that is resistant to Byzantine attacks and privacy leakages. Processing individual updates to manage adversarial behavior, while preserving privacy of data against colluding nodes, requires some sort of secure secret sharing. However, the communication load for secret sharing of long vectors of updates can be very high. In federated settings, where users are often edge devices with potential bandwidth constraints, excessive communication overhead is undesirable. ByzSecAgg solves this problem by partitioning local updates into smaller sub-vectors and sharing them using ramp secret sharing. However, this sharing method does not admit bi-linear computations, such as pairwise distance calculations, which are needed for distance-based outlier-detection algorithms, and effective methods for mitigating Byzantine attacks. To overcome this issue, each user runs another round of ramp sharing, with a different embedding of data in the sharing polynomial. This technique, motivated by ideas from coded computing, enables secure computation of pairwise distance. In addition, to maintain the integrity and privacy of the local update, ByzSecAgg also uses a vector commitment method, in which the commitment size remains constant (i.e., does not increase with the length of the local update), while simultaneously allowing verification of the secret sharing process. In terms of communication load, ByzSecAgg significantly outperforms the related baseline scheme, known as BREA.

Coded computing has proved to be useful in distributed computing, and has addressed challenges such as straggler workers. We have observed that almost all coded computing systems studied so far consider a setup of one master and some workers. However, recently emerging technologies such as blockchain, internet of things, and federated learning introduce new requirements for coded computing systems. In these systems, data is generated (and probably stored) in a distributed manner, so central encoding/decoding by a master is not feasible and scalable. This paper presents a multi-master distributed coded computing system that consists ofk∈ N data owners andN∈ N workers, where data owners employ workers to do some computations on their data, as specified by a target functionfof degreed∈ N. As there is no central encoder, workers perform encoding themselves, prior to computation phase. The challenge in this system is the presence of adversarial data owners that do not know the data of honest data owners but cause discrepancies by sending different versions of data to different workers, which is detrimental to local encodings in workers. There are at most β ∈ N adversarial data owners, and each distributes at mostv∈ N different versions of data. Since the adversaries and their possibly colluded behavior are not known to workers and honest data owners, workers compute tags of their received data, in addition to their main computational task, and send them to data owners in order to help them in decoding. We introduce a tag function that allows data owners to partition workers into sets that previously had received the same data from all data owners. Then, we characterize the fundamental limit of this multi-master distributed coded computing system, denoted byt*, which is the minimum number of workers whose work can be used to correctly calculate the desired function of data of honest data owners. We show thatt*=vβd(K− 1) + 1, and present converse and achievable proofs.

Coding theory revolves around the incorporation of redundancy into transmitted symbols, computation tasks, and stored data to guard against adversarial manipulation. However, error correction in coding theory is contingent upon a strict trust assumption. In the context of computation and storage, it is required that honest nodes outnumber adversarial ones by a certain margin. However, in several emerging real-world cases, particularly, in decentralized blockchain-oriented applications, such assumptions are often unrealistic. Consequently, despite the important role of coding in addressing significant challenges within decentralized systems, its applications become constrained. Still, in decentralized platforms, a distinctive characteristic emerges, offering new avenues for secure coding beyond the constraints of conventional methods. In these scenarios, the adversary benefits when the legitimate decoder recovers the data, and preferably with a high estimation error. This incentive motivates them to act rationally, trying to maximize their gains. In this paper, we propose a game theoretic formulation for coding, called the game of coding, that captures this unique dynamic where each of the adversaries and the data collector (decoder) have respective utility functions to optimize. The utility functions reflect the fact that both the data collector and the adversary are interested in increasing the chance of data being recoverable by the data collector. Moreover, the utility functions express the interest of the data collector to estimate the input with lower estimation error, but the opposite interest of the adversary. As a first, still highly non-trivial step, we characterize the equilibrium of the game for the repetition code with a repetition factor of 2 for a wide class of utility functions with minimal assumptions.

Estimating high-dimensional covariance matrices is crucial in various domains. This work considers a scenario where two collaborating agents access disjoint dimensions of $m$ samples from a high–dimensional random vector, and they can only communicate a limited number of bits to a central server, which wants to accurately approximate the covariance matrix. We analyze the fundamental trade–off between communication cost, number of samples, and estimation accuracy. We prove a lower bound on the error achievable by any estimator, highlighting the impact of dimensions, number of samples, and communication budget. Furthermore, we present an algorithm that achieves this lower bound up to a logarithmic factor, demonstrating its near-optimality in practical settings.

In this paper, we investigate the problem of transmitting an analog source to a destination over$N$uses of an additive-white-Gaussian-noise (AWGN) channel, where$N$is very small (in the order of 10 or even less). The proposed coding scheme is based on representing the source symbol using a novel progressive expansion technique, partitioning the digits of expansion into$N$ordered sets, and finally mapping the symbols in each set to a real number by applying the reverse progressive expansion. In the last step, we introduce some gaps between the signal levels to prevent the carry-over of the additive noise from propagation to other levels. This shields the most significant levels of the signal from an additive noise, hitting the signal at a less significant level. The parameters of the progressive expansion and the shielding procedure are opportunistically independent of the SNR so that the proposed scheme achieves a distortion$D$, where$-\log(D)$is within O(log log (SNR)) of the optimal performance for all values of SNR, leading to a channel-agnostic scheme.

Coding theory revolves around the incorporation of redundancy into transmitted symbols, computation tasks, and stored data to guard against adversarial manipulation. However, error correction in coding theory is contingent upon a strict trust assumption. In the context of computation and storage, it is required that honest nodes outnumber adversarial ones by a certain margin. However, in several emerging real-world cases, particularly, in decentralized blockchain-oriented applications, such assumptions are often unrealistic. Consequently, despite the important role of coding in addressing significant challenges within decentralized systems, its applications become constrained. Still, in decentralized platforms, a distinctive characteristic emerges, offering new avenues for secure coding beyond the constraints of conventional methods. In these scenarios, the adversary benefits when the legitimate decoder recovers the data, and preferably with a high estimation error. This incentive motivates them to act rationally, trying to maximize their gains. In this paper, we propose a game theoretic formulation for coding, called the game of coding, that captures this unique dynamic where each of the adversary and the data collector (decoder) have a utility function to optimize. The utility functions reflect the fact that both the data collector and the adversary are interested in increasing the chance of data being recoverable by the data collector. Moreover, the utility functions express the interest of the data collector to estimate the input with lower estimation error, but the opposite interest of the adversary. As a first, still highly non-trivial step, we characterize the equilibrium of the game for the repetition code with a repetition factor of 2, for a wide class of utility functions with minimal assumptions.

Coded computing has emerged as a promising framework for tackling significant challenges in large-scale distributed computing, including the presence of slow, faulty, or compromised servers. In this approach, each worker node processes a combination of the data, rather than the raw data itself. The final result then is decoded from the collective outputs of the worker nodes. However, there is a significant gap between current coded computing approaches and the broader landscape of general distributed computing, particularly when it comes to machine learning workloads. To bridge this gap, we propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a framework that seamlessly adapts with machine learning applications. In this framework, the objective is to find the encoder and decoder functions that minimize the loss function, defined as the mean squared error between the estimated and true values. Facilitating the search for the optimum decoding and functions, we show that the loss function can be upper-bounded by the summation of two terms: the generalization error of the decoding function and the training error of the encoding function. Focusing on the second-order Sobolev space, we then derive the optimal encoder and decoder. We show that in the proposed solution, the mean squared error of the estimation decays with the rate of $\mathcal{O}(S^3 N^{-3})$ and $\mathcal{O}(S^{\frac{8}{5}}N^{\frac{-3}{5}})$ in noiseless and noisy computation settings, respectively, where $N$ is the number of worker nodes with at most $S$ slow servers (stragglers). Finally, we evaluate the proposed scheme on inference tasks for various machine learning models and demonstrate that the proposed framework outperforms the state-of-the-art in terms of accuracy and rate of convergence.

We study a$K$-user coded-caching broadcast problem in a joint source-channel coding framework. The transmitter observes a database of files that are being generated at a certain rate per channel use, and each user has a cache, which can store a fixed fraction of the generated symbols. In the delivery phase, the transmitter broadcasts a message so that the users can decode their desired files using the received signal and their cache content. The communication between the transmitter and the receivers happens over a (deterministic) time-varying erasure broadcast channel, and the channel state information is only available to the users. We characterize the maximum achievable source rate for the 2-user and the degraded$K$-user problems. We provide an upper bound for any caching strategy’s achievable source rates. Finally, we present a linear programming formulation to show that the upper bound is not a sharp characterization. Closing the gap between the achievable rate and the optimum rate remains open.

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners. Proof-of-Stake chains are energy-efficient, have fast finality but face several security issues: susceptibility to non-slashable long-range safety attacks, low liveness resilience and difficulty to bootstrap from low token valuation. We show that these security issues are inherent in any PoS chain without an external trusted source, and propose a new protocol, Babylon, where an off-the-shelf PoS protocol checkpoints onto Bitcoin to resolve these issues. An impossibility result justifies the optimality of Babylon. A use case of Babylon is to reduce the stake withdrawal delay: our experimental results show that this delay can be reduced from weeks in existing PoS chains to less than 5 hours using Babylon, at a transaction cost of less than 10K USD per annum for posting the checkpoints onto Bitcoin.

We proposeSwiftAgg+, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of$N \in \mathbb {N}$distributed users, each of size$L \in \mathbb {N}$, trained on their local data, in a privacy-preserving manner.SwiftAgg+can significantly reduce the communication overheads without any compromise on security, and achieve optimal communication loads within diminishing gaps. Specifically, in presence of at most$D=o(N)$dropout users,SwiftAgg+achieves a per-user communication load of$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$symbols and a server communication load of$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$symbols, with a worst-case information-theoretic security guarantee, against any subset of up to$T=o(N)$semi-honest users who may also collude with the curious server. Moreover, the proposedSwiftAgg+allows for a flexible trade-off between communication loads and the number of active communication links. In particular, for$T< N-D$and for any$K\in \mathbb {N}$,SwiftAgg+can achieve the server communication load of$\left({1+\frac {T}{K}}\right)L$symbols, and per-user communication load of up to$\left({1+\frac {T+D}{K}}\right)L$symbols, where the number of pair-wise active connections in the network is$\frac {N}{2}(K+T+D+1)$.

One of the major challenges in using distributed learning to train complicated models with large data sets is to deal with stragglers effect. As a solution, coded computation has been recently proposed to efficiently add redundancy to the computation tasks. In this technique, coding is used across data sets, and computation is done over coded data, such that the results of an arbitrary subset of worker nodes with a certain size are enough to recover the final results. The major drawbacks with those approaches are (1) they are limited to polynomial functions, (2) the number of servers that we need to wait for grows with the degree of the model, (3) they are not numerically stable for computation over real numbers. In this paper, we propose Berrut Approximated Coded Computing (BACC), as an alternative approach, as a numerically stable solution, which works beyond polynomial functions computation and with any number of servers. The accuracy of the approximation is established theoretically and verified by simulation. In particular, BACC is used to train a deep neural network on a cluster of servers, which outperforms alternative uncoded solutions in terms of the rate of convergence.

In attribute-based access control, users with specific verified attributes will gain access to some particular data. Concerning the privacy of the users’ attributes, we study the problem of distributed attribute-based private access control (DAPAC) with multiple authorities. Each authority will learn and verify only one of the attributes.To investigate its fundamental limits, we introduce an information-theoretic DAPAC framework, with $N \in {\mathbb{N}},N \geq 2$, replicated non-colluding servers (authorities), and some users. Each user has an attribute vector ${{\mathbf{v}}^{\ast}} = \left( {v_1^{\ast}, \ldots,v_N^{\ast}} \right)$ of dimension N and is eligible to retrieve a message ${W^{{{\text{v}}^{\ast}}}}$, available on all servers. Each server n ∈ [N] can only observe and verify the n’th attribute of a user. In response, it sends a function of its authorized messages to the user. The system must satisfy the following conditions: (1) Correctness: the user with attribute vector v*can retrieve his intended message ${W^{{{\text{v}}^{\ast}}}}$ from the servers’ responses, (2) Data Secrecy: the user will not learn anything about the other messages, (3) Attribute Privacy: each Server n learns nothing beyond attribute n of the user. The capacity of the DAPAC is defined as the ratio of the file size and the aggregated size of the responses, maximized over all feasible schemes. We obtain a lower bound on the capacity of this problem by proposing an achievable algorithm with rate $\frac{1}{{2K}}$, where K is the size of the alphabet of each attribute.

We propose SwiftAgg, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of N distributed users, each of size L, trained on their local data, in a privacy-preserving manner. Compared with state-of-the-art secure aggregation protocols, SwiftAgg significantly reduces the communication overheads without any compromise on security. Specifically, in presence of at most D dropout users, SwiftAgg achieves a server communication load of (T +1)L and a per-user communication load of up to (T+D+1)L, with a worst-case information-theoretic security guarantee, against any subset of up to T semi-honest users who may also collude with the curious server. The key idea of SwiftAgg is to partition the users into groups of size T+D+1, then in the first phase, secret sharing and aggregation of the individual models are performed within each group, and then in the second phase, model aggregation is performed on T +D+1 sequences of users across the groups. If a user in a sequence drops out in the second phase, the rest of the sequence remains silent. This design allows only a subset of users to communicate with each other, and only the users in a single group to directly communicate with the server, eliminating the requirements of 1) all-to-all communication network across users; and 2) all users communicating with the server, for other secure aggregation protocols. This helps to substantially slash the communication costs of the system.

Sharding, i.e. splitting the miners or validators to form and run several subchains in parallel, is known as one of the main solutions to the scalability problems of blockchains. The drawback is that as the number of miners expanding each subchain becomes small, it becomes vulnerable to security attacks. To solve this problem, a framework, named as Ployshard, has been proposed in which each validator verifies a coded combination of the blocks introduced by different subchains, thus helping to protect the security of all subchains. In this paper, we introduce an attack on Ployshard, called the discrepancy attack, which is the result of malicious nodes controlling a few subchains and dispersing different blocks to different nodes. We show that this attack undermines the security of Polyshard and is undetectable in its current setting.

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, in particular for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to enable coding opportunities across intermediate results of different computation tasks to further reduce the communication load. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits the above two techniques (i.e., combining the intermediate results of the same computation and coding across the intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation (reduction) of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training algorithms where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme. Based on the compressed CDC technique, we then study a distributed training problem as one of its application. We characterize the communication load for this distributed training problem and show that it is asymptotically optimal.

We consider the problem of private information retrieval (PIR), where a single user with private side information (PSI) aims to retrieve multiple files from a library stored at some servers. We assume that the side information (SI) at the user includes a subset of files stored privately. Moreover, the identity of requests and side information at the user are not revealed to any of the servers. The problem involves finding the minimum load transmitted from the servers to the user such that the requested files can be decoded with the help of received data and side information. By providing matching lower and upper bounds for certain regimes, we characterize the minimum load imposed on all the servers. Our result shows that the capacity is the same as the capacity of a multi-message PIR problem without PSI, but with a library of reduced size, i.e., the library is equal to the original library size minus the size of SI. Finally, we extend our setup to the case where instead of storing complete files as SI, the user can store a fraction of files. For this scenario, we propose an achievability scheme based on which we discuss the best storing strategies.

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count-sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count-sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count-sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes. The proposed scheme provides an upper-bound on the recovery threshold as a function of the required accuracy of computation and the probability that the required accuracy can be violated. In addition, it provides an upper-bound on the recovery threshold for the case that the result of the multiplication is sparse, and the exact result is required.

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of$K \in \mathbb {N}$isolated source nodes and$N \in \mathbb {N}$encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by$\beta \in \mathbb {N}$, and the cardinality of the set of symbols that each one generates, denoted by$v \in \mathbb {N}$, the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of$t \in \mathbb {N}$encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is$t^{*} \in \mathbb {N}$, the minimum of such$t$, which is a function of$K$,$N$,$\beta $, and$v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that$t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$, if$N\ge K+2\beta (v-1)$, and$t^{*}_{\textrm {Linear}}=N$, if$N\le K+2\beta (v-1)$. In order to achieve$t^{*}_{\textrm {Linear}}$, we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node.

In this article, we consider a secure multi-party computation problem (MPC), where the goal is to offload the computation of an arbitrary polynomial function of some massive private matrices (inputs) to a cluster of workers. The workers are not reliable. Some of them may collude to gain information about the input data (semi-honest workers). The system is initialized by sharing a (randomized) function of each input matrix to each server. Since the input matrices are massive, each share's size is assumed to be at most 1/k fraction of the input matrix, for some k ∈ \mathbb N. The objective is to minimize the number of workers needed to perform the computation task correctly, such that even if an arbitrary subset of t-1 workers, for some t ∈ \mathbb N, collude, they cannot gain any information about the input matrices. We propose a sharing scheme, called polynomial sharing, and show that it admits basic operations such as adding and multiplication of matrices and transposing a matrix. By concatenating the procedures for basic operations, we show that any polynomial function of the input matrices can be calculated, subject to the problem constraints. We show that the proposed scheme can offer order-wise gain in terms of the number of workers needed, compared to the approaches formed by the concatenation of job splitting and conventional MPC approaches.

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals’ genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem ofassociated subsequence retrieval, where a dataset of N (possibly high-dimensional) sequences of length G, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from$\mathcal {X}^{\text {G}}$, where$\mathcal {X}$is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length$L$of the sequences, calledassociated subsequence. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of N sequences and their observable characteristics. We demonstrate that as the parameters N, G, and L grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as${{\it\text { Gh}}(\text {L}/\text {G})}/{\text {N}}$, where$\text {h}(\cdot )$is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the$\epsilon $-error-rate.

Software defined networking (SDN) is a promising technology in fifth generation wireless networks (5G) where due to the adoption of a centralized SDN-controller, resources such as processing and storage, can be utilized in an optimal manner. Although SDN was first considered with a logically centralized controller, due to delay, reliability, and scalability challenges, moving towards multiple distributed controllers is inevitable. In distributed control schemes, an assignment that associates a controller with each switch leads to three challenges of (1) Computational complexity, since the assignment is an NP-hard problem, (2) Resource and energy efficiency, to obtain an assignment with the lowest number of controllers in order to reduce resource and energy consumption, and (3) Dynamicity, where a dynamic approach of assignment is required to adapt to the network’s traffic changes. In this paper, we investigate the controller-switch assignment problem given the aforementioned challenges, and propose efficient algorithms for static and dynamic scenarios, that even achieve quantitative optimality guarantees in special cases. As shown through simulations, the proposed lower complexity algorithms not only outperform earlier works but also approach the performance of exhaustive search schemes, in some scenarios.

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, we introduce the problem of distributed encoding which is comprised of a set of K ∈ ℕ isolated source nodes and N ∈ ℕ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of adversarial nodes, denoted by β ∈ ℕ, and the cardinality of the set of symbols that each one generates, denoted by v ∈ ℕ, this would make the process of decoding from the encoded symbols impossible. Assume that a decoder connects to an arbitrary subset of t ∈ ℕ encoding nodes and wants to decode the symbol of honest nodes correctly, without necessarily identify the sets of honest and adversarial nodes. In this paper, we characterize t* ∈ ℕ, as the minimum of such t, as a function of K, N, β, and v. In particular, we show that for β ≥ 1, v ≥ 2, t* = K + β(v - 1) + 1, if N ≥ K + β(v -1) + 1, and t* = N, if N ≤ K + β(v - 1). Moreover, in order to achieve t*, linear encoding is not sufficient.

Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this article, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly logd rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(dϵ), a server complexity of O(d1+ϵ), a round complexity of O(logd) and an initialization complexity of O(d1+ϵ).

In this paper, we study the problem of private function computation, where a user wants to compute a function of some inputs, using N ∈ N servers, where the function is a private combination/composition of some K ∈ N public basic functions {f1, f2, ... , fK}. More precisely, for some inputs Wm, m ∈ [1 : M], the user's goal is to calculate h(Wm) = Σj=1J αjhj(Wm), for some J ∈ N, some scalers αj, j ∈ [1 : J], and some functions hj(.), j ∈ [1 : J], where each is an arbitrary compositions of the basic functions {f1, f2, ... , fK}. The computation is done through a sequence of queries to N servers. In each query, the user sends an input W, which is a (possibly randomized) function of W1:M and the answers to the previous queries, to one of the servers, and asks the server to return fk(W), for some k ∈ [1 : K]. The servers should not obtain any information about the structure of the function h(.), i.e., the way the basic functions are combined to form h(.), from the sequence of queries they received, even if T of them collude, for some T ∈ N. In this paper, we focus on the cases, where basic functions are linear and can be represented by (possibly large-scale) full-rank matrices, and each basic function may contribute in function h(.) for at most once. We prove that C, defined as the supremum of the number of desired computations of the basic functions, normalized by the number of queries, in asymptotic regimes of large M, satisfies the following inequality: min{(1-T/N)/(1-1/K), (1- T-1/N)}≤C≤1. The key idea is that in the proposed scheme, each server is asked to compute a specific order of basic functions, independent from the user's desired function. In addition, some random vectors are added to the inputs of the queries such that the sequence of the queries does not leak any information.

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of 2 of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations.

Current techniques in sequencing a genome allow a service provider (e.g. a sequencing company) to have full access to the genome information, and thus the privacy of individuals regarding their lifetime secret is violated. In this paper, we introduce the problem of private DNA sequencing, where the goal is to keep the DNA sequence private to the sequencer. We propose an architecture, where the task of reading fragments of DNA and the task of DNA assembly are separated, the former is done at the sequencer(s), and the later is completed at a local trusted data collector. To satisfy the privacy constraint at the sequencer and reconstruction condition at the data collector, we create an information gap between these two relying on two techniques: (i) we use more than one non-colluding sequencer, all reporting the read fragments to the single data collector, (ii) adding the fragments of some known DNA molecules, which are still unknown to the sequencers, to the pool. We prove that these two techniques provide enough freedom to satisfy both conditions at the same time.

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count-sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count-sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count-sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.

In this paper, we argue that in many basic algorithms for machine learning, including support vector machine (SVM) for classification, principal component analysis (PCA) for dimensionality reduction, and regression for dependency estimation, we need the inner products of the data samples, rather than the data samples themselves.Motivated by the above observation, we introduce the problem of private inner product retrieval for distributed machine learning, where we have a system including a database of some files, duplicated across some non-colluding servers. A user intends to retrieve a subset of specific size of the set of the inner product of every pair of data items in the database with minimum communication load, without revealing any information about the identity of the requested subset. For achievability, we use the algorithms for multi-message private information retrieval. For converse, we establish that as the length of the files becomes large, the set of all inner products converges to independent random variables with uniform distribution hence we find asymptotic capacity for this problem. We also derive the rate of this convergence. To prove that, we construct special dependencies among sequences of the sets of all inner products with different length, which forms a time-homogeneous irreducible Markov chain, without affecting the marginal distribution. We show that this Markov chain has a uniform distribution as its unique stationary distribution, with rate of convergence dominated by the second largest eigenvalue of the transition probability matrix. This allows us to develop a converse, which converges to a tight bound in some cases, as the size of the files becomes large.

A two-user coded caching problem is studied in a joint source-channel coding framework. A source generates symbols at a certain rate for each file in the database, and a fixed fraction of the symbols are cached at each user. The delivery phase of coded caching takes place over a time-varying erasure broadcast channel, where the channel state information is only available at the receivers. The maximum source rate to keep up with the ergodic rate of both users is characterized.

Coded caching is a new approach to decrease the communication load during the peak hours of the network. It provides a significant gain, that is maximized in the centralized setting, where the server controls the placement. In many situations, each user fills its cache without any information about the placement of other users. We show that subspace precoding for placement improves the delivery load of a decentralized caching system compared to uncoded placement. Surprisingly, the proposed scheme achieves the delivery load of the centralized placement for K = 3 users for the entire range of cache size.

This paper considers a cloud-RAN architecture with cache-enabled multi-antenna Edge Nodes (ENs) that deliver content to cache-enabled end-users. The ENs are connected to a central server via limited-capacity fronthaul links, and, based on the information received from the central server and the cached contents, they transmit on the shared wireless medium to satisfy users' requests. By leveraging cooperative transmission as enabled by ENs' caches and fronthaul links, as well as multicasting opportunities provided by users' caches, a close-to-optimal caching and delivery scheme is proposed. As a result, the minimum Normalized Delivery Time (NDT), a high-SNR measure of delivery latency, is characterized to within a multiplicative constant gap of 3/2 under the assumption of uncoded caching and fronthaul transmission, and of one-shot linear precoding. This result demonstrates the interplay among fronthaul links capacity, ENs' caches, and end-users' caches in minimizing the content delivery time.

In this paper, we introduce the problem of private sequential function computation, where a user wishes to compute a composition of a sequence of K linear functions, in a specific order, for an arbitrary input. The user does not run these computations locally, rather it exploits the existence of N noncolluding servers, each can compute any of the K functions on any given input. However, the user does not want to reveal any information about the desired order of computations to the servers. For this problem, we study the capacity, defined as the supremum of the number of desired computations, normalized by the number of computations done at the servers, subject to the privacy constraint. In particular, we show that the capacity satisfies (1- 1 N )/(1 - 1 max(K,N)) ≤ C ≤ 1. For the achievability, we show that the user can retrieve the desired order of computations, by choosing a proper order of inquiries among different servers, while keeping the order of computations for each server fixed, irrespective of the desired order of computations.

We consider the problem of interference management in wireless cellular networks with caches at both base stations and receivers, and we characterize the degrees of freedom (DoFs) per cell to within an additive gap of (1/3) and a multiplicative gap of 2 for all system parameters, under one-shot linear schemes. Our result indicates that the one-shot linear DoF per cell scales linearly with the total amount of cache available in the cell, i.e., the sum of the caches at the central base station and all the receivers within the cell, resembling a similar phenomenon previously observed for the case of fully connected wireless networks. To establish the result, we propose a decentralized and randomized cache placement and a delivery scheme, which, on one hand, utilizes the overlap of contents at the base station caches to zero-force part of their outgoing interference and, on the other hand, uses the receiver cache contents to create coded multicasting opportunities, so that the receivers can eliminate the remaining interference due to undesired packets. We also provide a converse argument, which shows that our achievable one-shot linear DoF per cell is within a constant additive gap of (1/3) and a multiplicative gap of 2 of its optimum.

In this paper, we consider K-user interference channels with M antennas per node and with backhaul collaboration in one side (among the transmitters or among the receivers), for M, K ∈ N, and investigate the tradeoff between the rate in the channel versus the communication load in the backhaul. In this investigation, each node is equipped with M antennas and we focus on a first order approximation result, where the rate of the wireless channel is measured by the degrees of freedom (DoF) per user, and the load of the backhaul is measured by the entropy of backhaul messages per user normalized by log of transmit power, at high power regimes. This tradeoff is fully characterized for the case of even values of K and approximately characterized for the case of odd values of K, with vanishing approximation gap as K grows. To achieve DoF of M per user, this result establishes the asymptotic optimality of the most straightforward scheme, called central processing, in which the messages are collected at one of the nodes, centrally processed, and forwarded back to each node. In addition, this result shows that the gain of the schemes, relying on distributed processing, through pairwise communication among the nodes (e.g., cooperative alignment) does not scale with the size of the network. For the converse, we develop a new outer-bound on the tradeoff based on splitting the set of collaborative nodes (transmitters or receivers) into two subsets and assuming full cooperation within each group. We further present a sufficient condition on the wireless channel connectivity, which although more relaxed, guarantees the validity of the above tradeoff. Finally, we show that verifying this condition takes a polynomial time in the network size.

We consider a basic caching system, where a single server with a database of N files (e.g., movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), improving the state of the arts that are within a factor of 4 and 4.7, respectively. Moreover, in a practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than five users and characterize the tradeoff within a factor of 2 otherwise. To establish these results, we develop two new converse bounds that improve over the state of the art.

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, especially for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to code across intermediate results of different tasks to further reduce communication. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits these two techniques (i.e., combining intermediate results of the same computation and coding across intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme.

In this paper, we introduce limited-sharing multiparty computation; in which there is a network of workers (processors) and a set of sources, each having access to a massive matrix as a private input. These sources aim to offload the task of computing a polynomial function of the matrices to the workers, while preserving the privacy of data. We also assume that the load of the link between each source and each worker is upper bounded by a fraction of each input matrix for some c ∈ {1, [1/2],[1/3], ...}. The objective is to minimize the number of workers needed to perform the computation, such that even if an arbitrary subset of t-1 workers, for some t ∈ N, collude, they cannot gain any information about the input matrices. This framework extends the conventional problem of multi-party computation, where the complexity of computation in each worker is not a constraint. We propose a novel sharing scheme, called polynomial sharing, and several procedures for basic operations such as adding and multiplication of two matrices, and transposing a matrix, and show that any polynomial function of the input matrices can be calculated using the proposed sharing algorithm and above procedures, subject to the problem constraints. We show that for basic operation such as addition and multiplication, the proposed scheme offers order wise gain, in terms of number of servers needed, compared to the approaches formed by concatenation of job splitting and conventional MPC approaches.

Coded caching can significantly decrease the communication load in peak hours of the network. The gain of caching is maximized in a centralized setting, where the cache content of users are opportunistically designed. In the absence of a centralized placement, users' caches are filled with randomly selected packets of the files. This yields to a loss in the caching gain, especially for small cache size. A novel placement scheme is introduced in this work which is based on (within file) precoding of the files at the server, followed by random cache placement. It is shown that the proposed technique improves the caching gain compared to the uncoded placement. Surprisingly, the performance of the proposed decentralized placement matches with that of the centralized placement for small cache size.

In the problem of population stratification, each data instance is generated based on a finite mixture model with$K$mixture components and$L$observed variables. Each variable takes its value in a finite state space with cardinality M. The variables are drawn independently in each mixture component. In this paper, we study the problem of the identifiability of parameters in this model, i.e. interpolation of the parameters of a mixture model from its mixture distribution. First we define the notion of informative variables. Then, we prove that the parameters of the problem are identifiable in the worst-case regime, if and only if the number of informative variables is greater than or equal to 2K − 1. As a result, in the worst-case analysis of the identifiability problem of finite mixture models, the number of required informative variables is Θ(K) and it is independent of the state space size.

In the problems of Genome-Wide Association Study (GWAS), the objective is to associate subsequences of individual's genomes to the observable characteristics called phenotypes. The genome containing the biological information of an individual can be represented by a sequence of lengthG. Many observable characteristics of the individuals can be related to a subsequence of a given lengthL, calledcausal subsequence. The environmental affects make the relation between the causal subsequence and the observable characteristics a stochastic function. Our objective in this paper is to detect the causal subsequence of a specific phenotype using a dataset ofNindividuals and their observed characteristics. We introduce an abstract formulation of GWAS which allows us to investigate the problem from an information theoretic perspective. In particular, as the parametersN,G, andLgrow, we observe a threshold effect at [(Gh(L/G))/N], whereh(.) is the binary entropy function. This effect allows us to define the capacity of recovering the causal subsequence by denoting the rate of the GWAS problem as [(Gh(L/G))/N]. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the ε-error-rate.

Consider massive matrix multiplication, a problem that underlies many data analytic applications, in a large-scale distributed system comprising a group of workers. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, designing intermediate computations at the workers in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We prove the optimality of entangled polynomial code in several cases, and show that it provides order-wise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code.

In a secure multiparty computation (MPC) system, there are some sources, where each one has access to a private input. The sources want to offload the computation of a polynomial function of the inputs to some processing nodes or workers. The processors are unreliable, i.e., a limited number of them may collude to gain information about the inputs. The objective is to minimize the number of required workers to calculate the polynomial, while the colluding workers gain no information about inputs. In this paper, we assume that the inputs are massive matrices, while the workers have the limited computation and storage at each worker. As proxy for that, we assume the link between each source and each worker admits a limited communication load. We propose a scheme for private data sharing, called entangled polynomial sharing, and show that it admits basic operations such as addition, multiplication, and transposing, respecting the constraint of the problem. Thus, it allows computing arbitrary polynomial of the input matrices, while it reduces the number of servers needed significantly compared to the conventional scheme. It also generalizes the recently proposed scheme of polynomial sharing.

We consider the problem of private information retrieval (PIR) where a single user with private side information aims to retrieve multiple files from a library stored (uncoded) at a number of servers. We assume the side information at the user includes a subset of files stored privately (i.e., the server does not know the indices of these files). In addition, we require that the identity of requests and side information at the user are not revealed to any of the servers. The problem involves finding the minimum load to be transmitted from the servers to the user such that the requested files can be decoded with the help of received and side information. By providing matching lower and upper bounds, for certain regimes, we characterize the minimum load imposed to all the servers (i.e., the capacity of this PIR problem). Our result shows that the capacity is the same as the capacity of a multi-message PIR problem without private side information, but with a library of reduced size. The effective size of the library is equal to the original library size minus the size of side information.

Genome-Wide Association Study (GWAS) addresses the problem of associating subsequences of individuals' genomes to the observable characteristics called phenotypes. In a genome of length G, it is observed that each characteristic is only related to a specific subsequence of it with length L, called the causal subsequence. The objective is to recover the causal subsequence, using a dataset of N individuals' genomes and their observed characteristics. Recently, the problem has been investigated from an information theoretic point of view in [1]. It has been shown that there is a threshold effect for reliable learning of the causal subsequence at [[Gh(L/G)]/N] by characterizing the capacity of it. Here h(.) denotes the binary entropy function. However, it is assumed that the dataset is collected from one population and the problem of mixed population datasets is not considered in [1], which is observed in many practical settings. In this paper, we study the mixed population version of GWAS, where we assume that the dataset is gathered from K subpopulations, rather than one. Each subpopulation has a specific causal subsequence for the observed characteristic and the subpopulation origins of individuals are latent. The objective is to recover all the causal subsequences with high accuracy. We investigate the fundamental limits of mixed population GWAS and characterize its capacity. It is observed that for a special class of two subpopulations, the capacity is one-fourth of the capacity of unmixed population case with the same parameters. Also, the capacity of this problem has connections to the capacity region of the Multiple Access Channel (MAC).

In future wireless networks, network functions virtualization lays the foundations for establishing a new dynamic resource management framework to efficiently utilize network resources. In this paper, a network service can be viewed as a chain of virtual network functions (VNFs), called a service function chain (SFC), served via placement, admission control (AC), and embedding into network infrastructure, based on the resource management objectives and the state of network. To fully exploit such a potential and reach higher network performance, resource management stages should be jointly performed. To this end, two main challenges are: how to present a system model that formulates the desired resource allocation problem for different types of SFCs as well as different features, and how to tackle the computational complexity of the problem and solve it in a tractable manner. In this paper, we address these two issues and solve the joint problem of AC and SFC embedding. We introduce a comprehensive system model, and formulate the joint task as a mixed integer linear programming. This formulation encompasses splittable VNF and multi-path routing scenarios. We employ relaxation, reformulation, and successive convex approximation methods to solve the problem. Simulation results demonstrate that the proposed schemes outperform the earlier works.

In this paper, we study the problem of delay minimization in network function virtualization-based networks. In such systems, the ultimate goal of any request is to compute a sequence of functions in the network, where each function can be computed at only a specific subset of network nodes. In conventional approaches, for each function, we choose one node from the corresponding subset of the nodes to compute that function. In contrast, in this paper, we allow each function to be computed in more than one node, redundantly in parallel, to respond to a given request. We argue that such redundancy in computation not only improves the reliability of the network but also, perhaps surprisingly, reduces the overall transmission delay. In particular, we establish that by judiciously choosing the subset of nodes which compute each function, in conjunction with a linear network coding scheme to deliver the result of each computation, we can characterize and achieve the optimal end-to-end transmission delay. In addition, we show that using such technique, it is possible to significantly reduce the transmission delay as compared to the conventional approaches. In fact, in some scenarios, such reduction can even scale with the size of the network, where by increasing the number of nodes that can compute the given function in parallel by a multiplicative factor, the end-to-end delay will also decrease by the same factor. Moreover, we show that while finding the subset of nodes for each computation, in general, is a complex integer program, approximation algorithms can be proposed to reduce the computational complexity. In fact, for the case where the number of computing nodes for a given function is upper bounded by a constant, a dynamic programming scheme can be proposed to find the optimum subsets in polynomial times. Our numerical simulations confirm the achieved gain in performance in comparison with conventional approaches.

How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and communication in distributed computing, i.e., the two are inversely proportional to each other. More specifically, a general distributed computing framework, motivated by commonly used structures like MapReduce, is considered, where the overall computation is decomposed into computing a set of “Map” and “Reduce” functions distributedly across multiple computing nodes. A coded scheme, named “coded distributed computing” (CDC), is proposed to demonstrate that increasing the computation load of the Map functions by a factor of r (i.e., evaluating each function at r carefully chosen nodes) can create novel coding opportunities that reduce the communication load by the same factor. An information-theoretic lower bound on the communication load is also provided, which matches the communication load achieved by the CDC scheme. As a result, the optimal computation-communication tradeoff in distributed computing is exactly characterized. Finally, the coding techniques of CDC is applied to the Hadoop TeraSort benchmark to develop a novel CodedTeraSort algorithm, which is empirically demonstrated to speed up the overall job execution by 1.97× -3.39×, for typical settings of interest.

We consider a basic cache network, in which a single server is connected to multiple users via a shared bottleneck link. The server has a database of files (content). Each user has an isolated memory that can be used to cache content in a prefetching phase. In a following delivery phase, each user requests a file from the database, and the server needs to deliver users' demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of the rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. In particular, we propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without any coordination.

We consider a problem of localizing the destination of an activated path signal supported on a graph. An “activated path signal” is a graph signal that evolves over time that can be viewed as the trajectory of a moving agent. We show that by combining dynamic programming and graph partitioning, the computational complexity of destination localization can be significantly reduced. Then, we show that the destination localization error can be upper-bounded using methods based on large-deviation. Using simulation results, we show a tradeoff between the destination localization error and the computation time. We compare the dynamic programming algorithm with and without graph partitioning and show that the computation time can be significantly reduced by using graph partitioning. The proposed technique can scale to the problem of destination localization on a large graph with one million nodes and one thousand time slots.

We consider the problem of interference management in wireless cellular networks with caches at both base stations and receivers and we characterize the degrees-of-freedom (DoF) per cell to within an additive gap of 1 and a multiplicative gap of 2 for all system parameters, under one-shot linear schemes. Our result indicates that the one-shot linear DoF per cell scales linearly with the total amount of cache that is available within each cell. A similar phenomenon had been previously observed for the case of fully-connected wireless networks. Hence, our result demonstrates that it also holds in cellular networks, despite the presence of path loss and fading which results in partial connectivity of the network topology. To establish the result, we propose a randomized and decentralized cache placement and a delivery scheme which, on one hand, utilizes the overlap of contents at base station caches to zero-force part of their outgoing interference, and on the other hand, uses the receiver caches to create coded multicasting opportunities, so that the receivers can eliminate the remaining interference due to undesired packets. We also provide a converse argument to show that our achievable one-shot linear DoF per cell is within an additive gap of 1 and a multiplicative gap of 2 of its optimal value.

To execute cloud computing tasks over a data center hosting hundreds of thousands of server nodes, it is natural to distribute computations across the nodes to take advantage of parallel processing. However, as we allocate more computing resources and further distribute the computations, a large amount of intermediate data must be moved between consecutive computation stages among the nodes, causing the communication load to become the bottleneck. In this paper, we study the optimal resource allocation in distributed computing, in order to minimize the total execution time accounting for the durations of both computation and communication phases. Particularly, we consider a general MapReduce-type framework, and focus on a recently proposed Coded Distributed Computing approach. For all values of problem parameters, we characterize the optimal number of servers that should be used for computing, provide the optimal placements of the Map and Reduce tasks, and propose an optimal coded data shuffling scheme. To prove the optimality of the proposed scheme, we first derive a matching information-theoretic converse on the execution time, then we prove that among all resource allocation schemes that achieve the minimum execution time, our proposed scheme uses the exactly least number of servers.

We consider a K-user Interference Channel where each transmitter is interested in conveying a message to its corresponding receiver. In addition, we assume a fully connected noiseless backhaul network through which receivers can collaborate and help each other recover their desired messages. In this paper, we fully characterize the trade-off between the rate in wireless link (per user) in terms of degrees of freedom (DoF) versus backhaul load (per user) for large values of K. In particular, we characterize the optimal trade-off for all values of K, where K is an even number. For odd values of K, we characterize the trade-off within a gap of 2(k - 1)/k(k + 1), which goes to zero as K increases. For achievability we use time-sharing between two corner points: (i) using interference alignment for the case where backhaul load is zero, and (ii) collecting a quantized version of all the received signals at one of the receivers to jointly decode the messages, for the case where DoF of one per user is desired. For the converse, we develop a new outer-bound based on the results from two-user multiple antenna interference channel with limited backhaul cooperation. Recently, it was shown that for the case of three-user interference channel, the optimal trade-off is achieved by some sort of alignment in the backhaul messaging, known as Cooperation Alignment. Our result shows that unlike the gain of interference alignment, the gain of cooperation alignment does not scale with the number of users K.

We consider a mobile edge computing problem, in which mobile users offload their computation tasks to computing nodes (e.g., base stations) at the network edge. The edge nodes compute the requested functions and communicate the computed results to the users via wireless links. For this problem, we propose a Universal Coded Edge Computing (UCEC) scheme for linear functions to simultaneously minimize the load of computation at the edge nodes, and maximize the physical-layer communication efficiency towards the mobile users. In the proposed UCEC scheme, edge nodes create coded inputs of the users, from which they compute coded output results. Then, the edge nodes utilize the computed coded results to create communication messages that zero-force all the interference signals over the air at each user. Specifically, the proposed scheme is universal since the coded computations performed at the edge nodes are oblivious of the channel states during the communication process from the edge nodes to the users.

We consider a system, containing a library of multiple files and a general memoryless communication network through which a server is connected to multiple users, each equipped with a local isolated cache of certain size that can be used to store part of the library. Each user will ask for one of the files in the library, which needs to be delivered by the server through the intermediate communication network. The objective is to design the cache placement (without prior knowledge of users' future requests) and the delivery phase in order to minimize the (normalized) delivery delay. We assume that the delivery phase consists of two steps: (1) generation of a set of multicast messages at the server, one for each subset of users, and (2) delivery of the multicast messages to the users. In this setting, we show that there exists a universal scheme for cache placement and multicast message generation, which is independent of the underlying communication network between the server and the users, and achieves the optimal delivery delay to within a constant factor for all memoryless networks. We prove this result, even though the capacity region of the underlying communication network is not known, even approximately. This result shows that in the aforementioned setting, a separation between caching and multicast message generation on one hand, and delivering the multicast messages to the users on the other hand is approximately optimal. This result has the important practical implication that the prefetching can be done independent of network structure in the upcoming delivery phase.

We consider a basic caching system, where a single server with a database of N files (e.g. movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), where the best proved characterization in the current literature gives a factor of 4 and 4.7 respectively. Moreover, in the practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than 5 users, and characterize the tradeoff within a factor of 2 otherwise. We establish these results by developing novel information theoretic outer-bounds for the caching problem, which improves the state of the art and gives tight characterization in various cases.

We consider a cache network, where a single server is connected to multiple users via a shared bottleneck link. The server has a set of files, which can be cached by each user in a prefetching phase. In a following delivery phase, each user requests a file and the server delivers user demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. We propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we can also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without coordination.

In this survey paper, we review three recent main results on cache networks, which not only considerably sharpen the approximate characterization of the rate-memory trade off, but also extend those results to more general networks. In these systems, a server with a database of some files (e.g. movies) is connected to multiple users via a communication network. Each user has an isolated memory of limited size that can be used for caching. The system operates in two phases: a placement phase where users each store a portion of the files in their local cache, and a delivery phase, where the users each request a file and the server delivers coded messages to the users, fulfilling their file requests. We start by considering the shared bottleneck network in two flavors of the system, with uncoded prefetching and with coded prefetching. First, for uncoded prefetching, an optimal design is proposed, under both centralized and decentralized settings, for both peak rate and average rate. The exact optimality is proven through a matching converse. Second, for caching with coded prefetching, we present a design that is optimal within a factor of approximately 2, which strictly improves the state of the art. Lastly, we move the focus to more general network topologies, and present an order-wise optimal scheme that is independent of the underlying communication network between the server and the users. This scheme is shown to achieve the minimum delivery delay with a constant factor for all memoryless networks.

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to optimally deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. This is the first code that achieves the optimal utilization of redundancy for tolerating stragglers or failures in distributed matrix multiplication. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics including computation latency and communication load. Moreover, we extend this code to distributed convolution and show its order-wise optimality.

We introduce the blind index coding (BIC) problem, in which a single sender communicates distinct messages to multiple users over a shared channel. Each user has partial knowledge of each message as side information. However, unlike classical index coding, in BIC, the sender is uncertain of what side information is available to each user. In particular, the sender only knows the amount of bits in each user's side information but not its content. This problem can arise naturally in caching and wireless networks. In order to blindly exploit side information in the BIC problem, we develop a hybrid coding scheme that XORs uncoded bits of a subset of messages with random combinations of bits from other messages. This scheme allows us to strike the right balance between maximizing the transmission rate to each user and minimizing the interference leakage to others. We also develop a general outer bound, which relies on a strong data processing inequality to effectively capture the senders uncertainty about the users' side information. Additionally, we consider the case where communication takes place over a shared wireless medium, modeled by an erasure broadcast channel, and show that surprisingly, combining repetition coding with hybrid coding improves the achievable rate region and outperforms alternative strategies of coping with channel erasure and while blindly exploiting side information.

We consider a system, comprising a library of N files (e.g., movies) and a wireless network with a KTtransmitters, each equipped with a local cache of size of MTfiles and a KRreceivers, each equipped with a local cache of size of MRfiles. Each receiver will ask for one of the N files in the library, which needs to be delivered. The objective is to design the cache placement (without prior knowledge of receivers' future requests) and the communication scheme to maximize the throughput of the delivery. In this setting, we show that the sum degrees-of-freedom (sum-DoF) of {(KTMT+KRMR)/N, KR} is achievable, and this is within a factor of 2 of the optimum, under uncoded prefetching and one-shot linear delivery schemes. This result shows that (i) the one-shot sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes), (ii) the transmitters' caches and receivers' caches contribute equally in the one-shot sum-DoF, and (iii) caching can offer a throughput gain that scales linearly with the size of the network. To prove the result, we propose an achievable scheme that exploits the redundancy of the content at transmitter's caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receiver's caches to cancel (subtract) some of the incoming interference. We develop a particular pattern for cache placement that maximizes the overall gains of cache-aided transmit and receive interference cancellations. For the converse, we present an integer optimization problem which minimizes the number of communication blocks needed to deliver any set of requested files to the receivers. We then provide a lower bound on the value of this optimization problem, hence leading to an upper bound on the linear one-shot sum-DoF of the network, which is within a factor of 2 of the achievable sum-DoF.

We study the capacity region of the two-user binary fading (or erasure) interference channel, where the transmitters have no knowledge of the channel state information. We develop new inner bounds and outer bounds for this problem. We identify three regimes based on the channel parameters: weak, moderate, and strong interference regimes. Interestingly, this is similar to the generalized degrees of freedom of the two-user Gaussian interference channel, where transmitters have perfect channel knowledge. We show that for the weak interference regime, treating interference as erasure is optimal while for the strong interference regime, decoding interference is optimal. For the moderate interference regime, we provide new inner and outer bounds. The inner bound is based on a modification of the Han-Kobayashi scheme for the erasure channel, enhanced by time-sharing. We study the gap between our inner bound and our outer bounds for the moderate interference regime and compare our results to that of the Gaussian interference channel. Deriving our new outer bounds has three main steps. We first create a contracted channel that has fewer states compared with the original channel, in order to make the analysis tractable. We then prove the correlation lemma that shows an outer bound on the capacity region of the contracted channel and also serves as an outer bound for the original channel. Finally, using the conditional entropy leakage lemma, we derive our outer bound on the capacity region of the contracted channel.

We consider a wireless distributed computing system, in which multiple mobile users, connected wirelessly through an access point, collaborate to perform a computation task. In particular, users communicate with each other via the access point to exchange their locally computed intermediate computation results, which is known as data shuffling. We propose a scalable framework for this system, in which the required communication bandwidth for data shuffling does not increase with the number of users in the network. The key idea is to utilize a particular repetitive pattern of placing the data set (thus a particular repetitive pattern of intermediate computations), in order to provide the coding opportunities at both the users and the access point, which reduce the required uplink communication bandwidth from users to the access point and the downlink communication bandwidth from access point to users by factors that grow linearly with the number of users. We also demonstrate that the proposed data set placement and coded shuffling schemes are optimal (i.e., achieve the minimum required shuffling load) for both a centralized setting and a decentralized setting, by developing tight information-theoretic lower bounds.

We propose a framework for edge-facilitated wireless distributed computing, in which several mobile users connected to an access point collaborate for a distributed computing task. We characterize the minimum communication load, both in uplink (from users to the access point) and downlink (from access point to the users), required for distributed computing. In particular, we develop a communication scheme and a dataset placement strategy that induces a particular overlap of computations at the users, which can then be exploited for coding at both users and the access point to significantly reduce the communication load. We demonstrate that the reduction in communication load (compared to uncoded solutions) can scale linearly with the size of the network (i.e., the number of users), hence our proposed scheme can result in a "scalable" design for edge- facilitated wireless distributed computing (i.e., accommodating any number of users without incurring extra communication load). Furthermore, we establish the optimality of the proposed scheme by developing a tight information theoretic outer- bound, and demonstrate that the proposed scheme achieves the minimum uplink and downlink communication load simultaneously. We also generalize the results to a decentralized setting, in which a random and a priori unknown subset of users may participate in distributed computing at each time, and characterize the minimum communication load for uniformly random dataset placement at users.

We consider a cellular wireless system including several interfering multi-user multi-antenna uplink channels, where the base station of each cell has to locally recover the messages of its corresponding users. We use a linear Wyner model, where each base station experiences interference only from the users in the two neighboring cells. Each base station is connected to the two nearby base stations through a backhaul link. The objective is to achieve the maximum degrees of freedom per cell, with minimum aggregated load in the backhaul. We propose a successive cooperative alignment scheme, in which each base station forms backhaul messages by combining the previous received backhaul messages with the received signals at its wireless terminal. By some alignment schemes in signaling over wireless links as well as developing proper messages over backhaul links, each base station can help the neighboring base stations to peel off the aggregated interference with minimum help. This is done without propagating interference throughout the network. In this conference paper, we focus on linear one shot schemes and prove the optimality of the proposed scheme, in a robust set-up for a system with two antennas per base station and two users per cell, where each user is equipped with two antennas.

We introduce a general distributed computing framework, motivated by commonly used structures like MapReduce, and formulate an information-theoretic tradeoff between computation and communication in such a framework. We characterize the optimal tradeoff to within a constant factor, for all system parameters. In particular, we propose a coded scheme, namely “Coded MapReduce” (CMR), which creates and exploits coding opportunities in data shuffling for distributed computing, reducing the communication load by a factor that is linearly proportional to the computation load. We then prove a lower bound on the minimum communication load, and demonstrate that CMR achieves this lower bound to within a constant factor. This result reveals a fundamental connection between computation and communication in distributed computing - the two are inverse-linearly proportional to each other.

We consider a system, comprising a library of files (e.g., movies) and a wireless network with an arbitrary number of transmitters and receivers, where each node is equipped with a local cache memory. The system operates in two phases, the prefetching phase, where each cache is pre-populated from the contents of the library, up to its limited size, and then the delivery phase, where each receiver reveals its request for a file from the library, and the system needs to deliver the requested files. The objective is to design the cache placement and the communication scheme to maximize the rate of delivery for arbitrary set of requested files. We characterize the sum degrees-of-freedom (sum-DoF) of this network to within a factor of 2 for all system parameters, under one-shot linear schemes. In particular, we show that the linear sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes). The proposed achievable scheme exploits the redundancy of the content at transmitters' caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receivers' caches to cancel (subtract) some of the incoming interference. The outer bound is derived by an optimization argument which bounds the number of communication blocks needed to deliver any requested contents to the receivers. This result demonstrates that in this setting, caches at the transmitters' side are equally valuable as the caches at the receivers' side. In addition, it shows that caching can offer a throughput gain that scales linearly with the size of the network.

We consider the problem of multiple-input single-output broadcast channels with Rayleigh fading where the transmitter has access to delayed knowledge of the channel state information. We first characterize the capacity region of this channel with two users to within constant number of bits for all values of the transmit power. The proposed signaling strategy utilizes the delayed knowledge of the channel state information and the previously transmitted signals, in order to create a signal of common interest for both receivers. This signal would be the quantized version of the summation of the previously transmitted signals. A challenge that arises in deriving the result for finite signal-to-noise ratio regimes is the correlation that exists between the quantization noise and the signal. To guarantee the independence of quantization noise and signal, we extend the framework of lattice quantizers with dither together with an interleaving step. For converse, we use the fact that the capacity region of this problem is upper bounded by the capacity region of a physically degraded broadcast channel with no channel state information where one receiver has two antennas. Then, we derive an outer bound on the capacity region of this degraded broadcast channel. Finally, we show how to extend our results to obtain the approximate capacity of the $K$ -user multiple-input single-output broadcast channel with delayed knowledge of the channel state information at the transmitter to within $2 \log _{2} ( K \,\, + 2 )$ bits/s/Hz.

Caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to locally deliver the part of the content, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider, in this paper, a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both the layers can simultaneously operate at approximately the minimum rate.

We consider a basic content distribution scenario consisting of a single origin server connected through a shared bottleneck link to a number of users each equipped with a cache of finite memory. The users issue a sequence of content requests from a set of popular files, and the goal is to operate the caches as well as the server such that these requests are satisfied with the minimum number of bits sent over the shared link. Assuming a basic Markov model for renewing the set of popular files, we characterize approximately the optimal long-term average rate of the shared link. We further prove that the optimal online scheme has approximately the same performance as the optimal offline scheme, in which the cache contents can be updated based on the entire set of popular files before each new request. To support these theoretical results, we propose an online coded caching scheme termed coded least-recently sent (LRS) and simulate it for a demand time series derived from the dataset made available by Netflix for the Netflix Prize. For this time series, we show that the proposed coded LRS algorithm significantly outperforms the popular least-recently used caching algorithm.

We introduce an index coding problem over wireless channels where a transmitter broadcasts to multiple receivers through an erasure channel, and receivers have access to some side-information unknown to the transmitter. Such scenarios can arise naturally, for example, in caching networks where users locally store popular files as side-information or in relay networks where users opportunistically overhear transmissions from multiple relays. For this problem, we present a coding scheme based on repetition coding combined with random linear coding, that allows us to send a message to one receiver while blindly exploiting side-information to control interference at the other. Within this class of coding schemes, we identify a tension between number of repetitions and random linear coding, characterize the achievable rate region, and compare the performance of our scheme against that of conventional methods.

Coded caching is a recently proposed technique that achieves significant performance gains for cache networks compared to uncoded caching schemes. However, this substantial coding gain is attained at the cost of large delivery delay, which is not tolerable in delay-sensitive applications such as video streaming. In this paper, we identify and investigate the tradeoff between the performance gain of coded caching and the delivery delay. We propose a computationally efficient caching algorithm that provides the gains of coding and respects delay constraints. The proposed algorithm achieves the optimum performance for large delay, but still offers major gains for small delay. These gains are demonstrated in a practical setting with a video-streaming prototype.

We introduce the “blind index coding” (BIC) problem, which generalizes the classic index coding problem by considering a sender that has some uncertainty about the side information that is available at each receiver. This problem naturally arises in wireless networks in which users obtain their side information through wireless channels with errors that may be unknown to the sender. For the proposed BIC problem, we develop a new general outer bound by first proving it for the 3-user case and then generalizing its construction to K users. The proof of the outer bound relies on developing a key lemma that uses a strong data processing inequality to account for the sender's uncertainty. We also propose a hybrid coding scheme that XORs random combinations of bits from a subset of messages with uncoded bits of other messages in order to blindly exploit side information, and illustrate its gain.

Over the past decade, the bulk of wireless traffic has shifted from speech to content. This shift creates the opportunity to cache part of the content in memories closer to the end users, for example in base stations. Most of the prior literature focuses on the reduction of load in the backhaul and core networks due to caching, i.e., on the benefits caching offers for the wireline communication link between the origin server and the caches. In this paper, we are instead interested in the benefits caching can offer for the wireless communication link between the caches and the end users. To quantify the gains of caching for this wireless link, we consider an interference channel in which each transmitter is equipped with an isolated cache memory. Communication takes place in two phases, a content placement phase followed by a content delivery phase. The objective is to design both the placement and the delivery phases to maximize the rate in the delivery phase in response to any possible user demands. Focusing on the three-user case, we show that through careful joint design of these phases, we can reap three distinct benefits from caching: a load balancing gain, an interference cancellation gain, and an interference alignment gain. In our proposed scheme, load balancing is achieved through a specific file splitting and placement, creating a particular pattern of content overlap at the caches. This overlap allows to implement interference cancellation. Further, it allows us to construct several virtual transmitters, each responsible for a part of the requested content, which increases interference alignment possibilities.

In this work, we consider an interference channel model in which K receivers cooperatively attempt to decode their intended messages locally by processing and sharing information through limited capacity backhaul links. In contrast to distributed antenna architectures that have been proposed in the literature, where data processing is utterly performed in a centralized fashion, the model considered in this paper aims to capture the essence of decentralized (over the cloud) processing, allowing for a more general class of interference management strategies. Focusing on the three-user case, we characterize the fundamental tradeoff between the achievable communication rates and the corresponding backhaul cooperation rate, in terms of degrees of freedom (DoF). Surprisingly, we show that the optimum communication-cooperation tradeoff remains the same when we move from two-user to three-user interference channels. In the absence of cooperation, this is due to interference alignment, which keeps the fraction of communication dimensions wasted for interference unchanged. When backhaul cooperation is available, we develop a new idea that we call cooperation alignment, which guarantees that the average (per user) backhaul load remains the same as we increase the number of users.

Interference alignment promises that, in Gaussian interference channels, each link can support half of a degree of freedom (DoF) per pair of transmit-receive antennas. However, in general, this result requires to precode the data bearing signals over a signal space of asymptotically large diversity, e.g., over an infinite number of dimensions for time-frequency varying fading channels, or over an infinite number of rationally independent signal levels, in the case of time-frequency invariant channels. In this paper, we consider a wireless cellular system scenario where the promised optimal DoFs are achieved with linear precoding in one-shot (i.e., over a single time-frequency slot). We focus on the uplink of a symmetric cellular system, where each cell is split into three sectors with orthogonal intrasector multiple access. In our model, interference is local, i.e., it is due to transmitters in neighboring cells only. We consider a noniterative local cooperation scheme where base stations pass to their neighbors their decoded messages such that interference from already decoded messages can be canceled. Therefore, for a given decoding order, the interference between sectors is described by a directed locally connected graph. The problem consists of maximizing the per-sector DoFs over all possible decoding orders and precoding schemes. In particular, we provide a decoding order and a one-shot interference alignment scheme able to achieve optimal per-sector DoFs, up to an additive gap due to boundary effects, that vanishes as the size of the network becomes large. Then, we extend our treatment by considering the case of intersector interference with joint processing of the three sector at each cell site. In order to avoid signaling schemes relying on the strength of interference, we further introduce the notion of topologically robust schemes, which are able to guarantee a minimum rate (or DoFs) irrespectively of the strength of the interfering links. Toward this end, we design a different decoding order and alignment scheme, which is topologically robust and still achieves the same optimum DoFs. Finally, we provide a new scheme for the downlink, based on local base station cooperation, where base stations pass to their neighbors a quantized version of their dirty-paper coded signals. For the proposed downlink scheme, we can prove a DoFs duality result showing that, for an appropriate choice of the precoding order and of the alignment beamforming vectors, it can achieve the same per-sector DoFs of the corresponding uplink schemes.

Although interference alignment (IA) can theoretically achieve the optimal degrees of freedom (DoFs) in the K-user Gaussian interference channel, its direct application comes at the prohibitive cost of precoding over exponentially many signaling dimensions. On the other hand, it is known that practical one-shot IA precoding (i.e., linear schemes without symbol expansion) provides a vanishing DoFs gain in large fully connected networks with generic channel coefficients. In our previous work, we introduced the concept of cellular IA for a network topology induced by hexagonal cells with sectors and nearest-neighbor interference. Assuming that neighboring sectors can exchange decoded messages (and not received signal samples) in the uplink, we showed that linear one-shot IA precoding over M transmit/ receive antennas can achieve the optimal M/2 DoFs per user. In this paper, we extend this framework to networks with omnidirectional (non-sectorized) cells and consider a limited practical scenario where users have 2 antennas, and base-stations have 2, 3, or 4 antennas. We provide linear one-shot IA schemes for the 2 × 2, 2 × 3, and 2 × 4 cases, and show the achievability of 3/4, 1, and 7/6 DoFs per user, respectively. DoFs converses for one-shot schemes require the solution of a discrete optimization problem over a number of variables that grows with the network size. We develop a new approach to transform such optimization problem into a tractable linear program with significantly fewer variables. This approach is used to show that 3/4 DoFs per user are indeed optimal for one-shot schemes over large (extended) cellular network with 2 × 2 links.

Replicating or caching popular content in memories distributed across the network is a technique to reduce peak network loads. Conventionally, the main performance gain of this caching was thought to result from making part of the requested data available closer to end-users. Instead, we recently showed that a much more significant gain can be achieved by using caches to create coded-multicasting opportunities, even for users with different demands, through coding across data streams. These coded-multicasting opportunities are enabled by careful content overlap at the various caches in the network, created by a central coordinating server. In many scenarios, such a central coordinating server may not be available, raising the question if this multicasting gain can still be achieved in a more decentralized setting. In this paper, we propose an efficient caching scheme, in which the content placement is performed in a decentralized manner. In other words, no coordination is required for the content placement. Despite this lack of coordination, the proposed scheme is nevertheless able to create coded-multicasting opportunities and achieves a rate close to the optimal centralized scheme.

We consider a basic content distribution scenario consisting of a single origin server connected through a shared bottleneck link to a number of users each equipped with a cache of finite memory. The users issue a sequence of content requests from a set of popular files, and the goal is to operate the caches as well as the server such that these requests are satisfied with the minimum number of bits sent over the shared link. Assuming a basic Markov model for renewing the set of popular files, we characterize approximately the optimal long-term average rate of the shared link. We further prove that the optimal online scheme has approximately the same performance as the optimal offline scheme, in which the cache contents can be updated based on the entire set of popular files before each new request. To support these theoretical results, we propose an online coded caching scheme termed coded least-recently sent (LRS) and simulate it for a demand time series derived from the dataset made available by Netflix for the Netflix Prize. For this time series, we show that the proposed coded LRS algorithm significantly outperforms the popular least-recently used (LRU) caching algorithm.

When several wireless users are sharing the spectrum, packet collision is a simple, yet widely used model for interference. Under this model, when transmitters cause interference at any of the receivers, their collided packets are discarded and need to be retransmitted. However, in reality, that receiver can still store its analog received signal and utilize it for decoding the packets in the future (for example, by successive interference cancellation techniques). In this work, we propose a physical layer model for wireless packet networks that allows for such flexibility at the receivers. We assume that the transmitters will be aware of the state of the channel (i.e. when and where collisions occur, or an unintended receiver overhears the signal) with some delay, and propose several coding opportunities that can be utilized by the transmitters to exploit the available signal at the receivers for interference management (as opposed to discarding them). We analyze the achievable throughput of our strategy in a canonical interference channel with two transmitter-receiver pairs, and demonstrate the gain over conventional schemes. By deriving an outer-bound, we also prove the optimality of our scheme for the corresponding model.

We consider the problem of broadcast over wireless erasure networks. To understand the challenges and opportunities of these setups, we study a two-hop erasure broadcast channel consisting of a single source, two relays, and two destinations desiring independent messages. In our network, no transmitter has channel state knowledge of erasures on outgoing links (i.e., no CSIT): The source has no knowledge of any channel state, each relay only has knowledge of the channel states of its incoming link, and destinations are provided with full channel knowledge. We propose a scheme, referred to as Align-and-Forward, that exploits the (unknown) common subspace of received signals at the relays, which results from the source-to-relay broadcast, in order to minimize the dimension of the interference subspace at each destination. We show that Align-and-Forward outperforms available alternative schemes in terms of sum-rate. We also present new outer-bounds and demonstrate the optimality of Align-and-Forward in certain regimes.

It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.

Interference alignment (IA) promises that, in Gaussian interference channels, each link can support half of a degree of freedom (DoF) per pair of transmit-receive antennas. However, in general, this result requires to precode the data bearing signals over a signal space of asymptotically large diversity, e.g., over an infinite number of dimensions in time-frequency for time-frequency varying fading channels. Here, we propose a communication scenario in wireless cellular systems where the promised optimal DoFs are achieved with linear precoding in one-shot (coding over a single time-frequency slot). We focus on uplink cellular systems, where each cell is split into three sectors and assume that interference is generated locally between transmitters and receivers of neighboring cells. We consider a message-passing network architecture, in which nearby sectors can exchange already decoded messages and propose an alignment solution that can achieve the optimal DoFs. To avoid signaling schemes relying on the strength of interference, we further introduce the notion of topologically robust schemes, which are able to guarantee a minimum rate (or degrees of freedom) no matter if the interference link are strong or weak. Towards this end, we design an alignment scheme which is topologically robust and still achieves the same optimum DoFs.

We characterize the capacity region of the symmetric two-user Binary Fading Interference Channel where transmitters have no knowledge of the channel state information. We show that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, and using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. The result is obtained by developing a novel outer-bound that has three main steps. We first create a contracted channel that has fewer states compared to the original channel, in order to make the analysis tractable. Using a Correlation Lemma, we then show that an outer-bound on the capacity region of the contracted channel also serves as an outer-bound for the original channel. Finally, using a Conditional Entropy Leakage Lemma, we derive our outer-bound on the capacity region of the contracted channel, and show that it coincides with the achievable region by either treat-interference-as-erasure or interference-decoding at each receiver.

Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e., the memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared with previously known schemes. In particular, the improvement can be on the order of the number of users in the network. In addition, we argue that the performance of the proposed scheme is within a constant factor of the information-theoretic optimum for all values of the problem parameters.

In this paper, we develop the machinery of real interference alignment. This machinery is extremely powerful in achieving the sum degrees of freedom (DoF) of single antenna systems. The scheme of real interference alignment is based on designing single-layer and multilayer constellations used for modulating information messages at the transmitters. We show that constellations can be aligned in a similar fashion as that of vectors in multiple antenna systems and space can be broken up into fractional dimensions. The performance analysis of the signaling scheme makes use of a recent result in the field of Diophantine approximation, which states that the convergence part of the Khintchine-Groshev theorem holds for points on nondegenerate manifolds. Using real interference alignment, we obtain the sum DoF of two model channels, namely the Gaussian interference channel (IC) and the X channel. It is proved that the sum DoF of the K-user IC is (K/2) for almost all channel parameters. We also prove that the sum DoF of the X-channel with K transmitters and M receivers is (K M/K + M - 1) for almost all channel parameters.

To study the effect of lack of up-to-date channel state information at the transmitters (CSITs), we consider two-user binary fading interference channels with Delayed-CSIT. We characterize the capacity region for such channels under homogeneous assumption, where channel gains have identical and independent distributions across time and space, eliminating the possibility of exploiting time/space correlation. We introduce and discuss several novel coding opportunities created by outdated CSIT that can enlarge the achievable rate region. The capacity-achieving scheme relies on accurate combination, concatenation, and merging of these opportunities, depending on the channel statistics. The outer-bounds are based on an extremal inequality we develop for a binary broadcast channel with delayed-CSIT. We further extend the results and characterize the capacity region when output feedback links are available from the receivers to the transmitters in addition to the delayed knowledge of the channel state information. We also discuss the extension of our results to the nonhomogeneous setting.

Caching is a technique to reduce peak traffic rates by prefetching popular content in memories at the end users. This paper proposes a novel caching approach that can achieve a significantly larger reduction in peak rate compared to previously known caching schemes. In particular, the improvement can be on the order of the number of end users in the network. Conventionally, cache memories are exploited by delivering requested contents in part locally rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e., the cache available at each individual user). In this paper, we introduce and exploit a second, global, caching gain, which is not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative cache available at all users), even though there is no cooperation among the caches. To evaluate and isolate these two gains, we introduce a new, information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, the proposed scheme exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared to previously known schemes. Moreover, we argue that the performance of the proposed scheme is within a constant factor from the information-theoretic optimum for all values of the problem parameters.

Interference alignment is a key technique for communication scenarios with multiple interfering links. In several such scenarios, interference alignment was used to characterize the degrees of freedom of the channel. However, these degree-of-freedom capacity approximations are often too weak to make accurate predictions about the behavior of channel capacity at finite signal-to-noise ratios (SNRs). The aim of this paper is to significantly strengthen these results by showing that interference alignment can be used to characterize capacity to within a constant gap. We focus on real, time-invariant, frequency-flat X-channels. The only known solutions achieving the degrees of freedom of this channel are either based on real interference alignment or on layer-selection schemes. Neither of these solutions seems sufficient for a constant-gap capacity approximation. In this paper, we propose a new communication scheme and show that it achieves the capacity of the Gaussian X-channel to within a constant gap. To aid in this process, we develop a novel deterministic channel model. This deterministic model depends on the 1/2 log (SNR) most-significant bits of the channel coefficients rather than only the single most-significant bit used in conventional deterministic models. The proposed deterministic model admits a wider range of achievable schemes that can be translated to the Gaussian channel. For this deterministic model, we find an approximately optimal communication scheme. We then translate this scheme for the deterministic channel to the original Gaussian X-channel and show that it achieves capacity to within a constant gap. This is the first constant-gap result for a general, fully-connected network requiring interference alignment.

Interference alignment is a key technique for communication scenarios with multiple interfering links. In several such scenarios, interference alignment was used to characterize the degrees-of-freedom of the channel. However, these degrees-of-freedom capacity approximations are often too weak to make accurate predictions about the behavior of channel capacity at finite signal-to-noise ratios. The aim of this paper is to significantly strengthen these results by showing that interference alignment can be used to characterize capacity to within a constant gap. We focus on real time-invariant frequency-flat X-channels, for which only the degrees-of-freedom are known. We propose a new communication scheme and show that it achieves the capacity of the Gaussian X-channel to within a constant gap. To aid in this process, we develop a novel deterministic channel model, admitting a wider range of achievable schemes that can be translated to the Gaussian channel. For this deterministic model, we find an approximately optimal communication scheme. We then translate this scheme for the deterministic channel to the original Gaussian X-channel and show that it achieves capacity to within a constant gap. This is the first constant-gap result for a fully-connected network requiring interference alignment.

In this paper, we study the capacity region of the two-user binary fading interference channel with delayed network state information at the transmitters and a noiseless output feedback link from each receiver to its corresponding transmitter. Our results include a new achievability strategy that systematically utilizes the stale network state information and the previously received signals at the receivers, in order to enhance the achievable rate region. We also derive new outer-bounds on the capacity region of such network, and we show that the delay in learning network state information results in some loss in the capacity region.

Transmitter channel state information (CSIT) is crucial for the multiplexing gains offered by advanced interference management techniques such as multiuser multiple-input multiple-output (MIMO) and interference alignment. Such CSIT is usually obtained by feedback from the receivers, but the feedback is subject to delays. The usual approach is to use the fed back information to predict the current channel state and then apply a scheme designed assuming perfect CSIT. When the feedback delay is large compared to the channel coherence time, such a prediction approach completely fails to achieve any multiplexing gain. In this paper, we show that even in this case, the completely stale CSI is still very useful. More concretely, we show that in an MIMO broadcast channel with$K$transmit antennas and$K$receivers each with 1 receive antenna,${{K}\over{1+{{1}\over{2}}+\ldots+{{1}\over{K}}}}(>1)$degrees of freedom is achievable even when the fed back channel state is completely independent of the current channel state. Moreover, we establish that if all receivers have independent and identically distributed channels, then this is the optimal number of degrees of freedom achievable. In the optimal scheme, the transmitter uses the fed back CSI to learn the side information that the receivers receive from previous transmissions rather than to predict the current channel state. Our result can be viewed as the first example of feedback providing a degree-of-freedom gain in memoryless channels.

We consider compound multiple-antenna broadcast channels with M transmit antennas and K single-antenna receivers, where the channel of receiver r takes one of Jrcomplex vectors. We show that for any finite Jr, the degrees of freedom (DoF) of MK/M+K-1 is achievable. It is in contrary to the commonly believed conjecture that the DoF collapses to one for large Jr's. We also establish the optimality of this result, where Jr≥ M, r = 1, ..., K. The achievable scheme relies on using a number theoretic approach of interference alignment, and ignoring the possibility of cooperation among the transmit antennas. Moreover, we show that if Jr's for some of the users are relatively small, then both transmit cooperation and interference alignment are needed. Unlike the conventional schemes, here the transmit precoders are not full rank.

We consider a problem of distributed lossy Gaussian source coding with inputs (y1, y2, y3), where y1and y2are positively correlated, y3= y1- cy2, c ≥ 0, and the decoder requires y3with a target distortion. For this problem, known achievable schemes are unboundedly loose. Inspired by results of binary expansion models, we characterize the rate-distortion region within a bounded gap. Treating each source as a multilayer input, an achievable scheme is developed based on the following observations: (i) some middle layers of y1and y2are not needed at the decoder, (ii) the required layers are combined with some unneeded interference information, (iii) linear operations among input layers can unboundedly reduce the load of reporting interference. Showing that the cut-set outer-bound has an unbounded gap, we also establish a new outer-bound to prove the bounded-gap result.

This paper aims at investigating the required feedback to achieve the Degrees of freedom (DoF) of X channel. Accordingly, a fixed precoding approach is proposed and is argued can achieve the DoF of such channel, assuming the channel state information is partially available at each transmitter through a feedback mechanism. This is achieved through using the notion of ergodic interference alignment technique. Accordingly, in a Rayleigh fading environment, it is shown a feedback rate of 2 log(p) + Θ(log log(p)) can achieve this DoF, where p is the total transmit power.

The rate-distortion region for the distributed source coding of the three jointly-Gaussian tree-structured sources with the quadratic distortion measure, is characterized within a constant gap. As a simplified counterpart of the Gaussian problem, we first investigate the rate region of a three binary-expanded sources where each pair of the sources have a certain number of the most-significant bits in common, and the central decoder needs to reconstruct each source with a target resolution. Motivated by the result of binary-expansion model, we prove that the achievable region of the quantize-and-binning scheme and the outer-bound of the cooperative scheme has a bounded gap of 2.4771 bits.

In this paper, a new Selective Mapping (SLM) technique is introduced for a Multiple-Input Multiple-Output (MIMO) broadcast (or MIMO point-to-point) system with channel inversion. We present a unified framework which links the problem of minimizing the average transmit energy from the constellation point of view, to the sum-rate maximization problem from the capacity viewpoint. First, we consider the point-to-point setup and derive the average transmit energy that can asymptotically be achieved by the proposed SLM technique. It is established that SLM achieves the minimum theoretical average transmit energy achievable by constellation shaping. Then, using the same idea, the average transmit energy in a broadcast system is derived and the relation between this value and the transmission rate is established. Finally, it is shown that the proposed SLM method can achieve the sum-capacity of the MIMO broadcast (or capacity of a MIMO point-to-point) channel at high SNR values.

For a wide class of multiuser systems, a subset of capacity region which includes the corner points and the sum-capacity facet has a special structure known as polymatroid. Multiple-access channels with fixed input distributions and multiple-antenna broadcast channels are examples of such systems. Any interior point of the sum-capacity facet can be achieved by time-sharing among corner points or by an alternative method known as rate-splitting. The main purpose of this paper is to find a point on the sum-capacity facet which satisfies a notion of fairness among the active users. This problem is addressed in two cases: (i) where the complexity of achieving interior points is not feasible, and (ii) where the complexity of achieving interior points is feasible. For the first case, the corner point for which the minimum rate of the active users is maximized is desired. A simple greedy algorithm is introduced to find such an optimum corner point. In addition, it is shown for single-antenna Gaussian multiple-access channels, the resulting corner point is leximin maximal with respect to the set of the corner points. For the second case, the properties of the unique leximin maximal rate vector with respect to the polymatroid are reviewed. It is shown that the problems of deriving the time-sharing coefficients or rate-splitting scheme to attain the leximin maximal vector can be solved by decomposing the problem into some lower dimensional subproblems. In addition, a fast algorithm to compute the time-sharing coefficients to attain a general point on the sum-capacity facet is presented.

In a multiple-antenna system with two transmitters and two receivers, a scenario of data communication, known as the X channel, is studied in which each receiver receives data from both transmitters. In this scenario, it is assumed that each transmitter is unaware of the other transmitter's data (noncooperative scenario). This system can be considered as a combination of two broadcast channels (from the transmitters' points of view) and two multiple-access channels (from the receivers' points of view). Taking advantage of both perspectives, two signaling schemes for such a scenario are developed. In these schemes, some linear filters are employed at the transmitters and at the receivers which decompose the system into either two noninterfering multiple-antenna broadcast subchannels or two noninterfering multiple-antenna multiple-access subchannels. The main objective in the design of the filters is to exploit the structure of the channel matrices to achieve the highest multiplexing gain (MG). It is shown that the proposed noncooperative signaling schemes outperform other known noncooperative schemes in terms of the achievable MG. In particular, it is shown that in some specific cases, the achieved MG is the same as the MG of the system if full cooperation is provided either between the transmitters or between the receivers.

A simple signaling method for broadcast channels with multiple-transmit multiple-receive antennas is proposed. In this method, for each user, the direction in which the user has the maximum gain is determined. The best user in terms of the largest gain is selected. The corresponding direction is used as the modulation vector (MV) for the data stream transmitted to the selected user. The algorithm proceeds in a recursive manner where in each step, the search for the best direction is performed in the null space of the previously selected MVs. It is demonstrated that with the proposed method, each selected MV has no interference on the previously selected MVs. Dirty-paper coding is used to cancel the remaining interference. For the case that each receiver has one antenna, the presented scheme coincides with the known scheme based on Gram-Schmidt orthogonalization (QR decomposition). To analyze the performance of the scheme, an upper bound on the cumulative distribution function (CDF) of each subchannel is derived which is used to establish the diversity order and the asymptotic sum-rate of the scheme. It is shown that using fixed rate codebooks, the diversity order of the jth data stream, 1 les j les M, is equal to N(M - j + 1)(K - j + 1), where M, N, and K indicate the number of transmit antennas, the number of receive antennas, and the number of users, respectively. Furthermore, it is proven that the throughput of this scheme scales as M log log(K) and asymptotically (K rarr infin) tends to the sum-capacity of the multiple-input multiple-output (MIMO) broadcast channel. The simulation results indicate that the achieved sum-rate is close to the sum-capacity of the underlying broadcast channel.

AK-user memoryless interference channel is considered where each receiver sequentially decodes the data of a subset of transmitters before it decodes the data of the designated transmitter. Therefore, the data rate of each transmitter depends on (i) the subset of receivers which decode the data of that transmitter, (ii) the decoding order, employed at each of these receivers. In this paper, a greedy algorithm is developed to find the users which are decoded at each receiver and the corresponding decoding order such that the minimum rate of the users is maximized. It is proven that the proposed algorithm is optimal.

A network of n communication links, operating over a shared wireless channel, is considered. Fading is assumed to be the dominant factor affecting the strength of the channels between transmitter and receiver terminals. It is assumed that each link can be active and transmit with a constant power P or remain silent. The objective is to maximize the throughput over the selection of active links. By deriving an upper bound and a lower bound, it is shown that in the case of Rayleigh fading: (i) the maximum throughput scales like log n; (ii) the maximum throughput is achievable in a distributed fashion. The upper bound is obtained using probabilistic methods, where the key point is to upper bound the throughput of any random set of active links by a chi-squared random variable. To obtain the lower bound, a decentralized link activation strategy is proposed and analyzed.

The capacity of time-varying channels with periodic feedback at the transmitter is evaluated. It is assumed that the channel-state information (CSI) is perfectly known at the receiver and is fed back to the transmitter at the regular time intervals. The system capacity is investigated in two cases: 1) finite-state Markov channel, and 2) additive white Gaussian noise channel with time-correlated fading. In the first case, it is shown that the capacity is achievable by multiplexing multiple codebooks across the channel. In the second case, the channel capacity and the optimal adaptive coding is obtained. It is shown that the optimal adaptation can be achieved by a single Gaussian codebook, while adaptively allocating the total power based on the side information at the transmitter.

For a wide class of multiuser systems, a subset of capacity region which includes the corner points and the sum-capacity facet has a special structure known as polymatroid. Any interior point of the sum-capacity facet can be achieved by time-sharing among corner points or by an alternative method known as rate-splitting. The main purpose of this paper is to find a point on the sum-capacity facet which satisfies a notion of fairness among active users. In one case, the corner point for which the minimum rate of the active users is maximized (max-min corner point) is computed for signaling. In another case, the polymatroid properties are exploited to locate a rate-vector on the sum-capacity facet which is optimally fair in the sense that the minimum rate among all users is maximized (max-min rate). It is shown that the problems of deriving the time-sharing coefficients or rate-splitting scheme can be solved by decomposing the problem to some lower-dimensional subproblems. In addition, a fast algorithm to compute the time-sharing coefficients to attain a general point on the sum-capacity facet is proposed

A new structure for multi-base systems is studied in which each user receives data from two nearby base stations, rather than only from the strongest one. This system can be considered as a combination of broadcast and multi-access channels. By taking advantages of both perspectives, an achievable rate region for a discrete memoryless channel modeled by Pr(y1,y2|x1,x2) is derived. In this model, x1and x2represent the transmitted signals by the transmitter one and two, respectively, and y1and y2denote the received signals by the receiver one and two, respectively. In this derivation, it is assumed that each transmitter is unaware of the data of the other transmitter, and therefore x1and x2are independent. To investigate the advantage of this scheme, an efficient signaling method which works at a corner point of the achievable region for multiple-antenna scenarios is developed. In the proposed scheme, each base station only requires the state information of the channels between the other base station and each user. In this paper, the signaling scheme is elaborated for the case that each transmitter/receiver is equipped with three antennas. It is proven that in such a scenario, the multiplexing gain of four is achievable, which outperforms any other conventional schemes

A full diversity block space-time code over two transmit antennas and two symbol periods is introduced. In this method, each code is equal to the addition of two matrices; A/sup m/ and DA/sup n/, where A and D are the two constant matrices and m and n are the two data symbols. A is selected such that the set A/sup m/, 0 /spl les/ m /spl les/ 2/sup b/ - 1 is closed under the matrix multiplication. This structure allows a simple maximum likelihood (ML) decoding method, and at the same time, simplifies the optimization of the coding advantage. Simulations show that the performance of the new code is very close to that of the Damen code (M. O. Damen et al., 2002) which is the best known block space-time code in terms of the coding advantage. Moreover, the decoding complexity of the proposed method is significantly lower than that of the Damen code.

This paper describes a new technique for timing synchronization in orthogonal frequency domain multiplexing (OFDM) transceiver systems. The proposed technique is based on non-synchronized sampling rate and no pilot is required to be transmitted. Therefore the transmission capacity is increased. The proposed algorithm employs the angles of the received symbols in the OFDM subchannels and provides a computationally efficient technique for estimation of the timing error. An equivalent state space model is also derived for timing error and then Kalman filtering method is exploited for tracking purposes. The proposed technique is very robust, particularly under low signal to noise ratio conditions and has been verified by means of computer simulations.