We consider a binary crowdsourcing problem in which independent tasks, such as fake-news detection or binary classification tasks, are assigned to$n$imperfect agents, each of which may misclassify/mislabel the tasks with some unknown probability. We revisit a result in [1], presented at NeurIPS 2017, regarding a lower bound for the minimax error of this problem, and then investigate a more general lower bound under a broader parameter set. We demonstrate that for any estimator using a sufficiently large number of independent observations$T$of the labeling results, the probability of having an estimation error of at least$1 / \sqrt{T}$is bounded away from zero by a constant that depends on a structural feature of the parameter set. Additionally, we derive a local version of this result, which essentially asserts that for any$r$-ball around any parameter point and any estimator based on$T \geq 4 / r^{2}$samples, there always exists a point in that ball that cannot be estimated accurately to within$o(1 / \sqrt{T})$.

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

In this work, we consider the problem of distributed matrix-vector product, where a server distributes the task of the computation among n worker nodes. In particular, it is assumed thatTmatrix-vector products have to be computed, where the matrix remains constant, whereas the vector changes each time. It is assumed thatLout of thenworkers are compromised (but non-communicating) and may return incorrect results to the task assigned to them. Moreover, these compromised workers are unreliable, that is, each compromised worker may return an incorrect and correct result with probabilities α and 1 − α, respectively, at any given time. The server aims to identify this set of unreliable compromised workers so that it can remove them from future computations. This work proposes and analyzes three probabilistic group testing schemes to achieve this: (i) a noise-level-independent non-adaptive scheme, (ii) a noise-level-dependent non-adaptive scheme, and (iii) a noise-level-dependent two-stage adaptive scheme. In particular, the third scheme is shown to be order-optimal, up to a constant multiplicative factor, for certain regimes of α andL. Using the proposed group testing schemes, sparse parity-check codes are constructed, which are used in the considered distributed computing framework for encoding, decoding, and identifying the unreliable workers. This methodology has two distinct features: (i) the computational cost of identifying the set ofLunreliable workers at the server is considerably lower than existing distributed computing methods in the literature, and (ii) the encoding and decoding functions are computationally efficient.

A novel coding design is proposed to enhance information retrieval in a wireless network of users with partial access to the data, in the sense of observation, measurement, computation, or storage. Information exchange in the network is assisted by a multi-antenna base station (BS), with no direct access to the data. Accordingly, the missing parts of data are exchanged among users through an uplink (UL) step followed by a downlink (DL) step. In this paper, new coding strategies, inspired by coded caching (CC) techniques, are devised to enhance both UL and DL steps. In the UL step, users transmit encoded and properly combined parts of their accessible data to the BS. Then, during the DL step, the BS carries out the required processing on its received signals and forwards a proper combination of the resulting signal terms back to the users, enabling each user to retrieve the desired information. Using the devised coded data retrieval strategy, the data exchange in both UL and DL steps requires the same communication delay, measured by normalized delivery time (NDT). Furthermore, the NDT of the UL/DL step is shown to coincide with the optimal NDT of the original DL multi-input single-output CC scheme, in which the BS is connected to a centralized data library.

In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of$F$families, each with$M$members. A number$k_{f}$out of the$F$families are infected, and a family is said to be infected if$k_{m}$out of its$M$members are infected. Furthermore, the sparsity constraint allows at most$\rho_{T}$individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When$k_{m}=\Theta(M)$and$M=\omega(\log(FM))$, our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature.

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.

We study a matrix completion problem which leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.

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.

We present a novel power-efficient and low-complexity scheme for cache-aided communication in networks with a multi-antenna base station that serves multiple single-antenna users. The scheme is based on transmitting coded messages to disjoint groups of users simultaneously and achieves an important trade-off between performance and complexity. The subpacketization level of the proposed scheme is sub-optimum compared to the state-of-the-art but is still feasible for a practical range of network parameters. On the other hand, the scheme achieves near-optimal performance and asymptotically achieves the same degrees of freedom (DoF) as the best-known schemes achieve. However, compared to other optimum achievable rates, the proposed scheme suffers from minor performance degradation due to power loss, which becomes negligible as the signal-to-noise ratio or the number of users grows. In return, the reductions in complexity and subpacketization allow for practical implementation of this scheme even for a large number of users. The presented scheme is also very flexible to the variation of the network topology and can easily be generalized to heterogeneous and dynamic scenarios.

The problem of distributed matrix-vector product is considered, where the server distributes the task of the computation among n worker nodes, out of which L are compromised (but non-colluding) and may return incorrect results. Specifically, it is assumed that the compromised workers are unreliable, that is, at any given time, each compromised worker may return an incorrect and correct result with probabilities α and 1−α, respectively. Thus, the tests are noisy. This work proposes a new probabilistic group testing approach t o identify the unreliable/compromised workers with $O\left( {\frac{{L\log (n)}}{\alpha }} \right)$ tests. Moreover, using the proposed group testing method, sparse parity-check codes are constructed and used in the considered distributed computing framework for encoding, decoding and identifying the unreliable workers. This methodology has two distinct features: (i) the cost of identifying the set of L unreliable workers at the server can be shown to be considerably lower than existing distributed computing methods, and (ii) the encoding and decoding functions are easily implementable and computationally efficient.

We formulate the problem of fake news detection using distributed inexpert agents. We consider the source for news/statements as a binary source (to model true vs. false statements). Upon observing news, each agent labels the news as true or false, which equals the validity of the statement with some probability depending on the reliability of the agent. In other words, each agent is viewed as a Binary Symmetric Channel (BSC) that misclassifies each statement with some error probability. For an algorithm that estimates the validity by thresholding a linear combination of the individual agents’ labels, we characterize the optimal weights and threshold to minimize the probability of error. We establish an upper bound on this probability of error as well as the naive majority rule.

This work uses non-adaptive probabilistic group testing to find a set of L defective items out of n items. In contrast to traditional group testing, in the considered setup each item can hide itself (or become inactive) during any given test with probability 1−α and is active with probability α. The authors of [Cheraghchi et al.] proposed an efficiently decodable probabilistic group testing scheme which requires $O\left( {\frac{{L\log (n)}}{{{\alpha ^3}}}} \right)$ tests for the per-instance scenario (where the group testing matrix works for any arbitrary, but fixed, set of L defective items) and $O\left( {\frac{{{L^2}\log (n/L)}}{{{\alpha ^3}}}} \right)$ tests for the universal scenario (where the same group testing matrix works for all possible defective sets of L items). The contribution of this work is two-fold: (i) with a slight modification in the construction of the group testing matrix proposed by [Cheraghchi et al.], the corresponding bounds on the number of sufficient tests are improved to $O\left( {\frac{{L\log (n)}}{{{\alpha ^2}}}} \right)$ and $O\left( {\frac{{{L^2}\log (n/L)}}{{{\alpha ^2}}}} \right)$ for the per-instance and universal scenarios respectively, while still using their efficient decoding method; and (ii) it is shown that the same bounds also hold for the fixed pool-size probabilistic group testing scenario, where in every test a fixed number of items are included for testing.

The information-theoretic secure exact-repair regenerating codes for distributed storage systems (DSSs) with parameters$(n,k=d,d,\ell)$are studied in this paper. We consider distributed storage systems with$n$nodes, in which the original data can be recovered from any subset of$k=d$nodes, and the content of any node can be retrieved from those of any$d$helper nodes. Moreover, we consider two secrecy constraints, namely, Type-I, where the message remains secure against an eavesdropper with access to the content of any subset of up to$\ell $nodes, and Type-II, in which the message remains secure against an eavesdropper who can observe the incoming repair data from all possible nodes to a fixed but unknown subset of up to$\ell $compromised nodes. Two classes of secure determinant codes are proposed for Type-I and Type-II secrecy constraints. Each proposed code can be designed for a range of per-node storage capacity and repair bandwidth for any system parameters. They lead to two achievable secrecy trade-offs, for Type-I and Type-II security.

We study a matrix completion problem that leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a low-rank matrix model for the rating matrix, and a hierarchical stochastic block model that well respects practically-relevant social graphs. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. Furthermore, we develop a matrix completion algorithm and empirically demonstrate via extensive experiments that the proposed algorithm achieves the optimal sample complexity.

This paper considers a distributed computing framework, where the task of T matrix-vector products is distributed among n worker machines. External adversaries have access to a subset ℒ (the cardinality of which is |ℒ|) of these machines, and can maliciously perturb the result of each of their computations with probability α. To correctly recover each matrixvector product, the master has to identify a set (of a fixed cardinality) of ‘unattacked’ worker machines. Towards this end, this work proposes four schemes that aim at performing such an identification. These schemes are analyzed and compared under different regimes of (|ℒ|,α) for the two cases when |ℒ| is (1) known or (2) unknown at the master.

This paper considers a diamond network with$n$interconnected relays, namely a network where a source communicates with a destination by hopping information through$n$communicating/interconnected relays. Specifically, the main focus of the paper is on characterizing sufficient conditions under which the$n$+ 1 states (out of the 2npossible ones) in which at most one relay is transmitting suffice to characterize the approximate capacity, that is the Shannon capacity up to an additive gap that only depends on n. Furthermore, under these sufficient conditions, closed form expressions for the approximate capacity and scheduling (that is, the fraction of time each relay should receive and transmit) are provided. A similar result is presented for the dual case, where in each state at most one relay is in receive mode.

We investigate a K-user parallel packet-erasure broadcast channel. There is an ongoing effort to harness millimeter-wave bands, which are known to be unstable having high outage probabilities, by combining them with stable legacy bands. Motivated by this effort, we consider a heterogeneous scenario in which the parallel subchannels are categorized into two classes having different outage probabilities. For the two-user case, we characterize the sum capacity by developing an explicit achievable scheme and deriving a matching upper bound. In contrast to suboptimal schemes that apply coding on a per-subchannel basis only, our scheme applies coding across subchannels to exploit coding opportunities that arise from asymmetric outage probabilities more efficiently, thereby achieving optimality. By extending our scheme systematically to be applicable for the K-user case, we show that it can provide significant gains over existing schemes. Compared to the K-user scheme currently employed in practice, which allocates chunks of subchannels to users exclusively, we demonstrate the performance improvement attainable by our scheme to be substantial, as the multiplicative gain scales with K. Moreover, we find that our scheme outperforms a per-subchannel extension of state-of-the-art K-user schemes by large margins, further reducing the optimality gap. Our results suggest a potential coding scheme that can be employed in future wireless systems to meet ever-growing mobile data demands.

Network Function Virtualization (NFV) is an efficient approach to simplify and accelerate the deployment of diverse network services. A critical challenge lies in mapping Virtual Network Functions (VNFs) to high-volume servers, resource allocation, and traffic routing. In this paper, we study the joint problem of VNF placement on servers and traffic engineering for a network spanning multiple subnetworks. Each subnetwork is owned and controlled by a different administrator. We formulate the joint problem of routing and VNF placement cost minimization subject to flow demands where processing flows in local subnetworks is encouraged. To ensure sensitive information of administrators remains private and to cut the implementation cost, a scalable and decentralized approach based on the proximal Alternating Direction Method of Multipliers (ADMM) is proposed. Extensive numerical evaluations show the efficiency of our approach against existing work.

We present a novel low complexity scheme for cache aided communication, where a multi-antenna base station serves multiple single-antenna mobiles. The scheme is based on transmission of coded messages to disjoint groups of users simultaneously. Compared to the state-of-the-art, the proposed scheme significantly reduces the transmission and decoding complexity. Furthermore, it substantially relaxes the subpacketization level, and involves a transmission of much smaller number of packets in each time block. The proposed scheme achieves the same degrees of freedom (DoF) as the best known scheme, but, it suffers from a performance degradation of about 1.5dB due to a loss of diversity. Nevertheless, the loss is acceptable as the reduction in complexity allows a practical implementation of this scheme even for a large number of users.

This paper considers the Gaussian half-duplex diamond n-relay network, which consists of a broadcast hop between the source and n relays, and of a multiple access hop between the relays and the destination. The n relays do not communicate with each other and operate in half-duplex mode. The main focus of the paper is on answering the following question: What fraction of the approximate capacity of the entire network can be retained by only operating the highest-performing single relay? It is shown that a fraction f = 1/(2 + 2cos (2π/n + 2)) of the approximate capacity of the entire network can always be guaranteed. This fraction is also shown to be tight, that is, there exist Gaussian half-duplex diamond n-relay networks for which exactly an f fraction of the approximate capacity of the entire network can be achieved by using only the highest-performing relay.

The secure exact-repair regenerating codes are studied, for distributed storage systems with parameters (n,k=d,d,ℓ). The secrecy constraint guarantees that the message remains secure against an eavesdropper who can observe the incoming repair data from all possible nodes to a fixed but unknown subset of (up to) ℓ compromised nodes (type II secrecy). A class of secure determinant codes are introduced for all system parameters, and an achievable secrecy trade-off between the per-node storage capacity and repair bandwidth is characterized.

This paper considers a diamond network with two interfering relays, where the source communicates with the destination via a layer of 2 half-duplex relays that can communicate with each other. The main focus is on characterizing the 3 relay receive/transmit configuration states (out of the 4 possible ones) that suffice to achieve the approximate capacity of the network. Towards this end, the binary linear deterministic approximation of the Gaussian noise channel is analyzed, and explicit scheduling and relaying schemes are presented. These schemes quantify the amount of information that each relay is responsible for sending to the destination, as well as the fraction of time each relay should receive and transmit.

We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering and then iteratively refines estimates both on graph clustering and matrix ratings. Under a hierarchical stochastic block model that well respects practically-relevant social graphs and a low-rank rating matrix model (to be detailed), we demonstrate that our algorithm achieves the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) that is derived by maximum likelihood estimation together with a lower-bound impossibility result. One consequence of this result is that exploiting the hierarchical structure of social graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. We conduct extensive experiments both on synthetic and real-world datasets to corroborate our theoretical results as well as to demonstrate significant performance improvements over other matrix completion algorithms that leverage graph side information.

We consider the data shuffling problem in a distributed learning system, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files, assuming the cached files are uncoded. The caches of the worker nodes are updated every iteration, and they should be designed to satisfy any possible unknown permutation of the files in subsequent iterations. For this problem, we characterize the exact load-memory trade-off for worst-case shuffling by deriving the minimum communication load for a given storage capacity per worker node. As a byproduct, the exact load-memory trade-off for any shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic coded shuffling scheme, which improves the state of the art, by exploiting the cache memories to create coded functions that can be decoded by several worker nodes. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.

A novel coding scheme for exact repair-regenerating codes is presented in this paper. The codes proposed in this work can trade between the repair bandwidth of nodes (number of downloaded symbols from each surviving node in a repair process) and the required storage overhead of the system. These codes work for general system parameters (n, k, d), which are the total number of nodes, the number of nodes suffice for data recovery, and the number of helper nodes in a repair process, respectively. The proposed construction offers a unified scheme to develop exact-repair regenerating codes for the entire trade-off, including the MBR and MSR points. We conjecture that the new storage-vs.-bandwidth trade-off achieved by the proposed codes is optimum. Some other key features of this code include: the construction is linear; the required field size is only Θ(n); and the code parameters and in particular sub-packetization level is at most (d - k +1)k; which is independent of the number of the parity nodes. Moreover, the proposed repair mechanism is helperindependent, that is the data sent from each helper only depends on the identity of the helper and failed nodes, but independent of the identity of other helper nodes participating in the repair process.

The binary number representation has dominated digital logic for decades due to its compact storage requirements. An alternative representation is the unary number system: We use N bits, from which the first M are 1 and the rest are 0 to represent the value M/N . One-hot representation is a variation of the unary number system where it has one 1 in the N bits, where the 1’s position represents its value. We present a novel method that first converts binary numbers to unary using thermometer (one-hot) encoders and then uses a “scaling network” followed by voting gates that we call “alternator logic,” followed by a decoder to convert the numbers back to the binary format. For monotonically increasing functions, the scaling network is all we need, which essentially uses only the routing resources and flip-flops on a typical FPGA architecture. Our method is clearly superior to the conventional binary implementation: Our area×delay cost is on average only 0.4%, 4%, and 39% of the binary method for 8-, 10-, and 12-bit resolutions, respectively, in thermometer encoding scheme, and 0.5%, 15%, and 147% in the one-hot encoding scheme. In terms of power efficiency, our one-hot method is between about 69× and 114× better compared to conventional binary.

Stochastic computing (SC) in recent years has been defined as a digital computation approach that operates on streams of random bits that represent probability values. SC can perform complex tasks with much smaller hardware footprints compared with conventional binary methods, but previous methods on SC circuits operated on serial bit streams, which leads to high-latency implementations. This article presents a significant improvement over previous work; it provides a deterministic parallel bit shuffling network that can use a simple deterministic thermometer encoding of data, resulting in zero random fluctuation and high accuracy, yet keeping the output bit-stream length constant. We use core “stochastic” logic circuits that do not employ constant coefficients, making them significantly smaller than traditional stochastic logic that use a significant amount of resources to generate such coefficients. Our experiments show that compared with previous SC methods, our method has up to 3x smaller mean absolute error, and better area x delay and power efficiency. Compared with conventional binary methods, our method is better in terms of area x delay at 8-bit resolution. It shows better power efficiency (40x, 18x, and 8x Gops/W at 8-, 10-, and 12-bit resolutions) compared with conventional binary.

This paper investigates the problem of how to efficiently operate Gaussian half-duplex diamond networks with N relays. It derives sufficient conditions that ensure that the network is operated close to its Shannon capacity, with a linear number in N (instead of exponential) of receive/transmit configuration states. Particularly, these states consist of having either at most one relay receiving or at most one relay transmitting. A transmission scheme is also designed and it is shown that, when the aforementioned conditions are satisfied, it achieves a rate that is to within a constant gap of the Shannon capacity. An appealing feature of the proposed scheme is that it offers guidelines on how to route the information through the relays so that the network operates close to its Shannon capacity.

1We present a construction for exact-repair regenerating codes with an information-theoretic secrecy guarantee against an eavesdropper with access to the content of (up to) ℓ nodes. The proposed construction works for the entire range of per-node storage and repair bandwidth for any distributed storage system with parameters (n, k = d, d, ℓ), aiming to maximize the size of the file that can be securely stored in the system. We provide an upper bound for the optimum trade-off for secure exact-repair regenerating codes.

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 studies a distributed computing setting in which the computing task consists of multiplying a matrix by a vector. A number of worker machines are attacked, i.e., the result of their computation is maliciously perturbed by some adversaries. In particular, the focus is on the case where these adversaries are non-colluding and non-communicating and hence they cannot jointly perturb the results of all the attacked worker machines. First, a condition that ensures that the result of the computing task can be successfully recovered with high probability is derived as a function of the setting parameters. Then, a probabilistic mechanism inspired by group testing is proposed to identify the set of the attacked worker machines, and the corresponding probability of error is derived.

Determinant codes are a class of exact-repair regenerating codes for distributed storage systems with parameters (n, k = d, d). These codes cover the entire trade-off between per-node storage and repair-bandwidth. In an earlier work of the authors, the repair data of the determinant code sent by a helper node to repair a failed node depends on the identity of the other helper nodes participating in the process, which is practically undesired. In this paper, a new repair mechanism is proposed for determinant codes, which relaxes this dependency, while preserving all other properties of the code. Moreover, it is shown that the determinant codes are capable of repairing multiple failures, with a per-node repair-bandwidth which scales sub-linearly with the number of failures.

Regenerating codes are efficient methods for distributed storage in storage networks, where node failures are common. They guarantee low cost data reconstruction and repair through accessing only a predefined number of arbitrarily chosen storage nodes in the network. In this paper, we consider two simultaneous extensions to the original regenerating codes framework introduced by Dimakis et al.; 1) both data reconstruction and repair are resilient to the presence of a certain number of erroneous nodes in the network and 2) the number of helper nodes in every repair is not fixed, but is a flexible parameter that can be selected during the run-time. We study the fundamental limits of required total repair bandwidth and provide an upper bound for the storage capacity of these codes under these assumptions. We then focus on the minimum repair bandwidth (MBR) case and derive the exact storage capacity by presenting explicit coding schemes with exact repair, which achieve the upper bound of the storage capacity in the considered setup. To this end, we first provide a more natural extension of the well-known product matrix (PM) MBR codes, modified to provide flexibility in choosing the number of helpers in each repair, and simultaneously be robust to erroneous nodes in the network. This is achieved by proving the non-singularity for a family of matrices in large enough finite fields. We next provide another extension of the PM codes, based on a novel repair scheme which enables flexibility in the number of helpers and robustness against erroneous nodes without any extra cost in field size compared with the original PM codes.

Stochastic Computing (SC) in recent years has been defined as a digital computation approach that operates on streams of random bits that represent probability values. In a bit-stream representing probability x, each bit has probability x of being 1. Using this simple assumption, SC can perform complex tasks with much smaller hardware footprints compared to conventional binary methods: e.g., a simple AND gate can perform multiplication between two uncorrelated bit-streams. Previous methods on SC circuits either relied on (1) randomness in the input bit streams, or (2) more recently, performing full convolution of deterministic streams to achieve exact computation results. The problem with the first method is that it introduces high random fluctuations and hence high variability in the results. The second method results in exponential increase in the length of the bit stream as circuit depth increases. Both of these methods suffer from very long latencies and neither is readily adaptable for parallel implementations. Our work presents a significant improvement over previous work: it provides a deterministic parallel bit shuffling network that can use a simple deterministic thermometer encoding of data, resulting in zero random fluctuation and high accuracy, yet keeping the output bit stream length constant. We use core “stochastic” logic circuits that do not employ constant coefficients, making them significantly smaller than traditional stochastic logic that potentially use a significant amount of resources to generate such constant coefficients. We show results on feed-forward and feedback circuits and show that our method on average has an area × delay value that is 10.6x smaller than of conventional binary and 7.9x smaller than previous stochastic work at 10-bit binary resolutions.

The binary number representation has dominated digital logic for decades due to its compact storage requirements. However, since the number system is positional, it needs to "unpack»» bits, perform computations, and repack the bits back to binary (\emphe.g., partial products in multiplication).An alternative representation is the unary number system: we use N bits, out of which the first M are 1 and the rest are 0 to represent the value $M/N$. We present a novel method which first converts binary numbers to unary using thermometer encoders, then uses a "scaling network»» followed by voting gates that we call "alternator logic»», followed by an adder tree to convert the numbers back to the binary format. For monotonically increasing functions, the scaling network is all we need, which essentially uses only the routing resources and flip-flops on the FPGA architecture. Our method is especially well-suited to FPGAs due to the abundant availability of routing and FF resources, and for the ability of FPGAs to realize high fanout gates for highly oscillating functions. We compare our method to stochastic computing and to conventional binary implementations on a number of functions, as well as on two common image processing applications. Our method is clearly superior to the conventional binary implementation: our area×delay cost is on average only 3%, 8% and 32% of the binary method for 8-, 10-, and 12-bit resolutions respectively. Compared to stochastic computing, our cost is 6%, 5%, and 8% for those resolutions. The area cost includes conversions from and to the binary format. Our method out performs the conventional binary method on an edge detection algorithm. However, it is not competitive with the binary method on the median filtering application due to the high cost of generating and saving unary representations of the input pixels.

We consider the data shuffling problem, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files. We characterize the exact rate-memory trade-off for the worst-case shuffling under the assumption that cached files are uncoded, by deriving the minimum communication rate for a given storage capacity per worker node. As a byproduct, the exact rate-memory trade-off for any random shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic and systematic coded shuffling scheme, which improves the state of the art. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.

A novel class of exact-repair regenerating codes is introduced for a distributed storage system with arbitrary parameters (n, k, d). The proposed construction is based on the optimum determinant codes for (n, k=d, d) systems. This construction yields an achievable trade-off between the storage and the repair bandwidth, consisting of k corner points, which meets the optimum trade-off at the MBR and MSR points, and improves all the previously known bounds for interior points. The sub-packetization level of the proposed code only depends on k and d, but not number of nodes n. Further, the required field size for the proposed code is Θ(n). We conjecture that the proposed codes can universally achieve the optimum trade-off.

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.

The RAID-6 configuration is more tolerant of disk failures than other RAID levels because of its ability to tolerate two disk failures. However, previous RAID-6 codes suffer from two major overheads - the time of encoding or decoding processes plus the need to access multiple blocks when updating parities or recovering failed blocks. For example, the PS and Reed-Solomon codes do not have optimal computation complexity, while P-code, X-code and RDP-code must access multiple blocks to update parities during write operations. This work proposes a new XOR- based RAID-6 code, called Tier-code, which not only achieves the optimal parity computation complexity, but also increases the write and degraded-mode read performance compared to previous codes. It uses two tiers of coding, one at the block level and the other at the chunk level. Experimental results of software testing, simulation and ASIC synthesis for this new hierarchical code demonstrate that Tier-code can outperform the previous RAID-6 codes in both write performance and degraded-mode read performance while maintaining the optimal computation complexity in both hardware and software implementations.

We study the problem of cache-aided communication for cellular networks with multi-user and multiple antennas at finite signal-to-noise ratio. Users are assumed to have non-symmetric links, modeled by wideband fading channels. We show that the problem can be formulated as a linear program, whose solution provides a joint cache allocation along with pre-fetching and fetching schemes that minimize the duration of the communication in the delivery phase. The suggested scheme uses zero-forcing and cached interference subtraction, and hence, allows each user to be served at the rate of its own channel. Thus, this scheme is better than the previously published schemes that are compromised by the poorest user in the communication group. We also consider a special case of the parameters for which we can derive a closed form solution and formulate the optimal power, rate, and cache optimization. This special case shows that the gain of MIMO coded caching goes beyond the throughput. In particular, it is shown that in this case, the cache is used to balance the users such that fairness and throughput are no longer contradicting. More specifically, in this case, strict fairness is achieved jointly with maximizing the network throughput.

In the distributed storage systems (DSSs) with k systematic nodes, robustness against node failure is commonly provided by storing redundancy in a number of other nodes and performing repair mechanism to reproduce the content of the failed nodes. Efficiency is then achieved by minimizing the storage overhead and the amount of data transmission required for data reconstruction and repair, provided by coding solutions, such as regenerating codes. Common explicit regenerating code constructions enable efficient repair through accessing a predefined number, d, of arbitrary chosen available nodes, namely helpers. In practice, however, the state of the system dynamically changes based on the request load, the link traffic, and so on, and the parameters which optimize system's performance vary accordingly. It is then desirable to have coding schemes which are able to operate optimally under a range of different parameters simultaneously. Specifically, adaptivity in the number of helper nodes for repair is of interest. While robustness requires capability of performing repair with small number of helpers, it is desirable to use as many helpers as available to reduce the transmission delay and total repair traffic. In this paper, we focus on the minimum storage regenerating (MSR) codes, where each of the n nodes in the network is supposed to store α information units, and the source data of size kα could be recovered from any arbitrary set of k nodes. We introduce a class of MSR codes that realize the optimal repair bandwidth simultaneously with a set of different choices for the number of helpers, namely D = {d1, . . . , dδ}. Our coding scheme follows the product matrix (PM) framework introduced by Rashmi et al. and could be considered as a generalization of the PM MSR code presented by Rashmi et al., such that any di= (i + 1)(k - 1) helpers can perform an optimal repair. As a result, the coding rate in our construction is limited by (k/n) ≤ (1/2). However, similar to the original design of PM MSR codes, our solution can realize practical values of the parameter α. Recently, Ye and Barg have presented another explicit MSR coding scheme which is capable of performing optimal repair for various number of helpers. The solution presented by Ye and Barg works for any arbitrary set of parameters k and D and can achieve high-coding rates, but the required α for this code is exponentially large. We show that the required value for α in the coding scheme presented in this paper is exponentially smaller when compared with the work of Ye and Barg for the same set of other parameters. Particularly, for a DSS with n nodes and k systematic nodes, the required value for α is reduced from sn to sk, where s = 1 cm(d1-k+1, ⋯, dδ-k+1). We also show the required field size in the presented coding scheme is equal to n.

This paper focuses on the design of regeneration codes. An (n, k, d) exact-regenerating code encodes and stores the data into n nodes such that the entire data can be recovered from any k nodes, and the missing coded information of any failed node can be identically recovered by the help of d nodes. In an earlier work of the authors, determinant codes are introduced for any (n, k, d = k) system, and they are shown to achieve the optimum tradeoff between the node storage α and the repair-bandwidth β In this work, the latter constraint of d = k is relaxed, and the construction of determinant codes is generalized to arbitrary parameters (n, k, d), for a certain range of (α, β). The proposed construction is scalable, in the sense that the system performance only depend on k and d, and the same of operating point (α, β) can be universally achieved for any number of nodes n. The resulting codes are linear, and the required size of the underlying finite field is not greater than Θ(n).

We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.

Motivated by recent efforts to harness millimeter-wave (mmWave) bands, known to have high outage probabilities, we explore a K-user parallel packet-erasure broadcast channel that consists of orthogonal subchannels prone to packet-erasures. Our main result is two-fold. First, in the homogeneous channel where all subchannels have the same erasure probability, we show that the separation principle holds, i.e., coding across subchannels provides no gain. Second, in the heterogeneous channel where the subchannels have different erasure probabilities, we devise a scheme that employs coding across subchannels and show that the principle fails to hold, i.e., coding across subchannels provides a gain. Inspired by this finding, we demonstrate our scheme to be effective in harnessing the mmWave bands. Compared to the current approach in the 4G systems which allocates subchannels to users exclusively, we show that our scheme offers a huge gain. We find the gain to be significant in scenarios where the erasure probabilities are largely different, and importantly to increase with the growth of K. Our result calls for joint coding schemes in future wireless systems to meet growing mobile data demands.

In coding for distributed storage systems, efficient data reconstruction and repair through accessing a predefined number of arbitrarily chosen storage nodes is guaranteed by regenerating codes. Traditionally, code parameters, specially the number of helper nodes participating in a repair process, are predetermined. However, depending on the state of the system and network traffic, it is desirable to adapt such parameters accordingly in order to minimize the cost of repair. In this work a class of regenerating codes with minimum storage is introduced that can simultaneously operate at the optimal repair bandwidth, for a wide range of exact repair mechanisms, based on different number of helper nodes.

Variant calling, in particular, calling SNPs (Single Nucleotide Polymorphisms) is a fundamental task in genomics. While existing packages offer excellent performance on calling SNPs which have uniquely mapped reads, they suffer in loci where the reads are multiply mapped, and are unable to make any reliable calls. Variants in multiply mapped loci can arise, for example in long segmental duplications, and can play important role in evolution and disease. In this paper, we develop a new SNP caller named abSNP, which offers three innovations. (a) abSNP calls SNPs from RNA-Seq data. Since RNA-Seq data is primarily sampled from gene regions, this method is inexpensive. (b) abSNP is able to successfully make calls on repetitive gene regions by exploiting the quality scores of multiply mapped reads carefully in order to make variant calls. (c) abSNP exploits a specific feature of RNA-Seq data, namely the varying abundance of different genes, in order to identify which repetitive copy a particular read is sampled from. We demonstrate that the proposed method offers significant performance gains on repetitive regions in simulated data. In particular, the algorithm is able to achieve near-perfect sensitivity on high-coverage SNPs, even when multiply mapped.

The exact-repair regeneration codes for distributed storage system are studied in this work. A novel coding scheme is proposed for code construction for any (n, k, d = k) system, and it is shown to be optimal. In particular, the optimum tradeoff of exact-repair regeneration system is fully characterized for any system with d = k. The new construction is based on fundamental properties of matrix determinant, thus the code is called determinant code. It is devised for the entire range of (α, β) on the optimum tradeoff.

We explore the role of a relay in multiuser networks where some physical perturbation shared around the users may generate data traffic for them simultaneously, hence cause their transmission patterns to be correlated. We investigate how the gain from the help of a relay varies with correlations across the users' transmission patterns in a bursty multiple access channel where the users send signals intermittently. As our main results, we show that in most cases a relay can provide a greater degrees-of-freedom (DoF) gain when the users' transmission patterns are more correlated. Furthermore, we demonstrate that the DoF gain can scale with the number of users.

Regenerating codes are efficient methods for distributed storage in practical networks where node failures are common. They guarantee low cost data reconstruction and repair through accessing only a predefined number of arbitrary chosen storage nodes in the network. In this work we study the fundamental limits of required total repair bandwidth and the storage capacity of these codes under the assumption that i) both data reconstruction and repair are resilient to the presence of a certain number of erroneous nodes in the network and ii) the number of helper nodes in every repair is not fixed, but is a flexible parameter that can be selected during the run-time. We focus on the minimum repair bandwidth point in this work, propose the associated coding scheme to posses both these extra properties, and prove its optimality.

The exact-repair regenerating codes for distributed storage system are studied in this work. A novel coding scheme is proposed for code construction for any (n, k, d = k) system. It is shown that the proposed codes are optimum, in the sense that any operating point satisfying the lower bound for the storage-bandwidth trade-off can be achieved with the proposed construction. As a consequence, the optimum linear trade-off of exact-regenerating system is fully characterized for any systems with d = k. The proposed codes are linear, and can be generated by multiplication of an encoder matrix with a so-called data matrix. The exact regenerating property is provided based on fundamental properties of matrix determinants, and in particular, generalized Laplace expansion for determinant. Thus the code is called determinant code. Importantly, the field size required for this code construction is 8(n), the total number of nodes in the system.

Characterizing the exact repair storage-vs-repair bandwidth tradeoff for distributed storage systems remains an open problem for more than four storage nodes. Motivated by the prevalence and practical applicability of linear codes, the exact repair problem when restricted to linear codes is considered. The main result of this paper is a new approach to develop bounds for exact repair distributed storage systems with linear codes (LDSS). Using this approach, the exact repair region for the (k + 1, k, k) LDSS is completely characterized. The new approach utilizes the properties of linear codes together with the exact repair constraints. These constraints are formally captured through an optimization problem with a recursive structure, and its solution finally yields the new bounds for the LDSS. These bounds together with recent code constructions characterize the exact repair region for (k + 1, k, k) LDSS.

The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.

The reference-based DNA shotgun assembly problem is studied from an information-theoretic point of view. The entire sequence has to be assembled based on a reference sequence which is a noisy version of the desired one, and a set of short reads sampled from the desired sequence. Two necessary conditions on the underlying parameters for reconstruction are obtained. A reference-based assembly algorithm is proposed, and it is shown that under these conditions the algorithm can reconstruct the sequence with high probability.

The symmetricK-user interference channel with fully connected topology is considered, in which 1) each receiver suffers interference from all other (K-1) transmitters, and 2) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (\ssrGDoF) is characterized in terms of α, where the interference-to-noise ratio (\ssrINR) is given by \ssrINR= \ssrSNRα. It is shown that the per-user \ssrGDoFof this network is the same as that of the two-user interference channel with feedback, except for α = 1, for which existence of feedback does not help in terms of \ssrGDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding. Moreover, an approximate characterization is provided for the symmetric feedback capacity of the network, when the \ssrSNRand \ssrINRare far apart from each other.

TheK-user cyclic Z-interference channel models a situation in which thekth transmitter causes interference only to the (k-1)th receiver in a cyclic manner, e.g., the first transmitter causes interference only to theKth receiver. The impact of noiseless feedback on the capacity of this channel is studied by focusing on the Gaussian cyclic Z-interference channel. To this end, the symmetric feedback capacity of the linear shift deterministic cyclic Z-interference channel is completely characterized for all interference regimes. Using insights from the linear deterministic channel model, the symmetric feedback capacity of the Gaussian cyclic Z-interference channel is characterized up to within a constant number of bits. As a byproduct of the constant gap result, the symmetric generalized degrees of freedom with feedback for the Gaussian cyclic Z-interference channel are also characterized. These results highlight that the symmetric feedback capacities for both linear and Gaussian channel models are in general functions ofK, the number of users. Furthermore, the capacity gain obtained due to feedback decreases asKincreases.

The two-user multiple-input multiple-output (MIMO) interference channel (IC) with arbitrary numbers of antennas at each terminal is considered and the degrees of freedom (DoF) region is characterized in the presence of noiseless channel output feedback from each receiver to its respective transmitter and availability of delayed channel state information at the transmitters (CSIT). It is shown that having output feedback and delayed CSIT can strictly enlarge the DoF region of the MIMO IC when compared to the case in which only delayed CSIT is present. The proposed coding schemes that achieve the corresponding DoF region with feedback and delayed CSIT utilize both resources, i.e., feedback and delayed CSIT in a nontrivial manner. It is also shown that the DoF region with local feedback and delayed CSIT is equal to the DoF region with global feedback and delayed CSIT, i.e., local feedback and delayed CSIT is equivalent to global feedback and delayed CSIT from the perspective of the DoF region. The converse is proved for a stronger setting in which the channels to the two receivers need not be statistically equivalent.

The degrees of freedom (DoF) region of the two-user MIMO interference channel (IC) is completely characterized in the presence of noiseless channel output feedback from each receiver to its respective transmitter and with the assumption of delayed channel state information (CSI) at the transmitters. It is shown that having output feedback and delayed CSI at the transmitters can strictly enlarge the DoF region when compared to the case in which only delayed CSI is available at the transmitters. Furthermore, cases are identified in which output feedback and delayed CSI alone are sufficient to achieve the DoF region achievable with perfect, instantaneous CSI.

The symmetric K user interference channel with fully connected topology is considered, in which (a) each receiver suffers interference from all other K - 1 transmitters, and (b) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (GDoF) is characterized in terms of α, where the interference-to-noise ratio (INR) is given by INR = SNRα. It is shown that the number of per-user GDoF of this network is the same as that of the 2-user interference channel with feedback, except for α = 1, for which existence of feedback does not help in terms of GDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding.

The sum degrees of freedom (DoF) of the two-user MIMO X-channel is characterized in the presence of output feedback and delayed channel state information (CSI). The number of antennas at each transmitters is assumed to be M and the number of antennas at each of the receivers is assumed to be N. It is shown that the sum DoF of the two-user MIMO X-channel is the same as the sum DoF of a two-user MIMO broadcast channel with 2M transmit antennas, and N antennas at each receiver. Hence, for this symmetric antenna configuration, there is no performance loss in the sum degrees of freedom due to the distributed nature of the transmitters. This result highlights the usefulness of feedback and delayed CSI for the MIMO X-channel. The K-user X-channel with a single antenna at each transmitter and each receiver is also studied. In this network, each transmitter has a message intended for each receiver. For this network, it is shown that the sum DoF with partial output feedback alone is at least 2K/(K + 1). This lower bound is strictly better than the best lower bound known for the case of delayed CSI assumption for all values of K.

Nonadaptive group testing involves grouping arbitrary subsets of n items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most d defective items. Motivated by applications in network tomography, sensor networks and infection propagation, a variation of group testing problems on graphs is formulated. Unlike conventional group testing problems, each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper, a test is associated with a random walk. In this context, conventional group testing corresponds to the special case of a complete graph on n vertices. For interesting classes of graphs a rather surprising result is obtained, namely, that the number of tests required to identify d defective items is substantially similar to what is required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph G, it is shown that with m = O(d2T2(n) log(n/d)) nonadaptive tests, one can identify the defective items. Consequently, for the Erdos-Rényi random graph G(n, p), as well as expander graphs with constant spectral gap, it follows that m = O(d2log3n) non-adaptive tests are sufficient to identify d defective items. Next, a specific scenario is considered that arises in network tomography, for which it is shown that m = O(d3log3n) nonadaptive tests are sufficient to identify d defective items. Noisy counterparts of the graph constrained group testing problem are considered, for which parallel results are developed. We also briefly discuss extensions to compressive sensing on graphs.

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

A cascade lossy source coding problem with one encoder and two decoders is considered. All variations of this problem are studied by varying the availability of correlated side information at the encoder/decoder(s). The set of achievable rate-distortion triples is characterized for three instances of this problem when the encoder is interested in transmission of a memoryless equiprobable binary source X subject to Hamming distortion and the side information Y is an erased version of X.

This paper addresses the problem of finding the nearest neighbor (or one of the $R$-nearest neighbors) of a query object $q$ in a database of $n$ objects, when we can only use a comparison oracle. The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. The main problem we study is how to search the database for the nearest neighbor (NN) of a query, while minimizing the questions. The difficulty of this problem depends on properties of the underlying database. We show the importance of a characterization: \emph{combinatorial disorder} $D$ which defines approximate triangle inequalities on ranks. We present a lower bound of $\Omega(D\log \frac{n}{D}+D^2)$ average number of questions in the search phase for any randomized algorithm, which demonstrates the fundamental role of $D$ for worst case behavior. We develop a randomized scheme for NN retrieval in $O(D^3\log^2 n+ D\log^2 n \log\log n^{D^3})$ questions. The learning requires asking $O(n D^3\log^2 n+ D \log^2 n \log\log n^{D^3})$ questions and $O(n\log^2n/\log(2D))$ bits to store.

In this study, the authors consider the class of anti-uniform Huffman (AUH) codes. The authors derived tight lower and upper bounds on the average codeword length, entropy and redundancy of finite and infinite AUH codes in terms of the alphabet size of the source. These bounds are tighter than similar bounds. Also a tight upper bound on the entropy of AUH codes is presented in terms of the average cost of the code. The Fibonacci distribution is introduced, which plays a fundamental role in AUH codes. It is shown that such distributions maximise the average length and the entropy of the code for a given alphabet size. The authors also show that the minimum average cost of a code is achieved by an AUH codes in a highly unbalanced cost regime.

In this paper, we study a Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows between different source-destination pairs. We focus on two-stage relay-interference networks where there are weak cross links, causing the networks to behave like a chain ofZGaussian channels. Our main result is an approximate characterization of the capacity region for such ZZ and ZS networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. This scheme in conjunction a new network decomposition technique provides the approximate characterization. Our analysis of these Gaussian networks is based on insights gained from an exact characterization of the corresponding linear deterministic model.

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized linear network coding operations on the source packets. We propose a channel model for the noncoherent network coding introduced by Koetter and Kschischang in , that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.

Non-adaptive group testing involves grouping arbitrary subsets of n items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagation we formulate non-adaptive group testing problems on graphs. Unlike conventional group testing problems each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper we associate a test with a random walk. In this context conventional group testing corresponds to the special case of a complete graph on n vertices. For interesting classes of graphs we arrive at a rather surprising result, namely, that the number of tests required to identify d defective items is substantially similar to that required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph G, we show that with m = O(d2T2(n) log(n/d)) non-adaptive tests, one can identify the defective items. Consequently, for the Erdõs-Rényi random graph G(n, p), as well as expander graphs with constant spectral gap, it follows that m = O(d2log3n) non-adaptive tests are sufficient to identify d defective items. We next consider a specific scenario that arises in network tomography and show that m = O(d3log3n) non-adaptive tests are sufficient to identify d defective items. We also consider noisy counterparts of the graph constrained group testing problem and develop parallel results for these cases.

In this paper we consider communication from a source to a destination over a wireless network with the help of a set of authenticated relays. We focus on a special “diamond” network, where there is no direct link between the source and the destination; however the relay nodes help to establish such a communication. There is a single adversarial node which injects signals to disrupt this communication. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. This is done by developing an outer bound, and demonstrating an achievable strategy that is within a constant number of bits of the outer bound, regardless of the channel values. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.

We consider the asymmetric multilevel diversity (A-MLD) coding problem, where a set of2K- 1 information sources, ordered in a decreasing level of importance, is encoded intoKmessages (or descriptions). There are2K- 1 decoders, each of which has access to a nonempty subset of the encoded messages. Each decoder is required to reproduce the information sources up to a certain importance level depending on the combination of descriptions available to it. We obtain a single letter characterization of the achievable rate region for the 3-description problem. In contrast to symmetric multilevel diversity coding, source-separation coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Based on the intuitions gained in treating the A-MLD problem, we derive inner and outer bounds for the rate region of the asymmetric Gaussian multiple description (MD) problem with three descriptions. Both the inner and outer bounds have a similar geometric structure to the rate region template of the A-MLD coding problem, and, moreover, we show that the gap between them is constant, which results in an approximate characterization of the asymmetric Gaussian three description rate region.

Compressed sensing (CS) deals with the reconstruction of sparse signals from a small number of linear measurements. One of the main challenges in CS is to find the support of a sparse signal from a set of noisy observations. In the CS literature, several information-theoretic bounds on the scaling law of the required number of measurements for exact support recovery have been derived, where the focus is mainly on random measurement matrices. In this paper, we investigate the support recovery problem from an estimation theory point of view, where no specific assumption is made on the underlying measurement matrix. By using the Hammersley-Chapman-Robbins (HCR) bound, we derive a fundamental lower bound on the performance of any unbiased estimator which provides necessary conditions for reliable ¿2-norm support recovery. We then analyze the optimal decoder to provide conditions under which the HCR bound is achievable. This leads to a set of sufficient conditions for reliable ¿2-norm support recovery.

In this paper we study the Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We examine this problem for certain regimes of channel values, when one of the cross-links is dominated by noise, resulting in Z and/or S configurations for the networks. For these Gaussian ZZ and ZS networks, we establish an approximate characterization of the rate region. The outer bounds to the capacity regions are established using genie-aided techniques that extend the methods used for the Gaussian interference channel to the relay-interference network. For the inner bound of the ZZ network, we utilize a new interference management scheme, termed interference neutralization, which was inspired by our earlier study of such deterministic networks. This technique allows for over-the-air interference removal, without the transmitters having complete access to the interfering signals.

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ¿ 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.

In this paper we consider communication between two special nodes (ldquosourcerdquo and ldquodestinationrdquo) in a wireless relay network, which has malfunctioning or malicious nodes (inserting errors). We develop the model for wireless network communication in the presence of a Byzantine adversary for different assumptions on channel/adversarial knowledge. We examine coding schemes which utilize signal interactions in the deterministic wireless network to reliably deliver information in the presence of such errors due to a Byzantine adversary.

The wireless multiple-unicast problem is considered over a layered network, where the rates of transmission are limited by the relaying and interference effect. The deterministic model introduced is used to capture the broadcasting and multiple access effects. The capacity region of the Z-chain relay-interference network is fully characterized. In order to solve the problem, we introduce a new achievability scheme based on ldquointerference neutralizationrdquo and a new analysis technique to bound the number of non-interfering (pure) signals.

We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1- delta2), where deltaiis what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.

We consider multiple description (MD) coding for the Gaussian source withKdescriptions under the symmetric mean-squared error (MSE) distortion constraints, and provide an approximate characterization of the rate region. We show that the rate region can be sandwiched between two polytopes, between which the gap can be upper-bounded by constants dependent on the number of descriptions, but independent of the distortion constraints. Underlying this result is an exact characterization of the lossless multilevel diversity source coding problem: a lossless counterpart of the MD problem. This connection provides a polytopic template for the inner and outer bounds to the rate region. In order to establish the outer bound, we generalize Ozarow's technique to introduce a strategic expansion of the original probability space by more than one random variable. For the symmetric rate case with any number of descriptions, we show that the gap between the upper bound and the lower bound for the individual description rate-distortion function is no larger than 0.92 bit. The results developed in this work also suggest that the ldquoseparationrdquo approach of combining successive refinement quantization and lossless multilevel diversity coding is a competitive one, since its performance is only a constant away from the optimum. The results are further extended to general sources under the MSE distortion measure, where a similar but looser bound on the gap holds.

Symmetric multilevel diversity coding was introduced by Roche et al, where a set of K information sources is encoded by K encoders and the decoders reconstruct sources 1,...,k, where k is the number of encoders to which they have access. In this paper, we formulate an asymmetric multilevel diversity coding problem, where a set of 2K- 1 information sources is encoded by K encoders into K streams/descriptions. There are 2K- 1 decoders, each of which has access to a non-empty subset of the encoded messages. The decoders are assigned with ordered levels, and each of them has to decode a subset of the information sources, according to its level, which depends on the set of encoders to which it has access, not just the cardinality. We obtain a single letter characterization of the complete achievable rate region for the 3- description problem. In doing so, we show that it is necessary to jointly encode independent sources (i.e., similar to network coding), and that linear codes are optimal for this problem.

We consider symmetric multiple description coding for the Gaussian source, and provide upper and lower bounds for the individual description rate-distortion function. One of the main contributions of this work is a novel lower bound on the sum rate under symmetric distortion constraints, which yields a lower bound on the individual rate for the symmetric case. Two upper bounds are derived, the first of which is based on successive refinement coding coupled with multilevel diversity coding (SR-MLD), and the second is based on the multi-layer coding scheme proposed in literature. We show that the gaps between the lower bound and the upper bounds are no larger than certain constants depending only on the number of descriptions, but not the distortion constraints. Moreover, regardless of the number of descriptions, the gap between the lower bound and the upper bound using the SR-MLD coding scheme is less than 1.5 bits, and for the other case, the gap is less than 1 bit.

We consider asymmetric multiple description (MD) source coding for Gaussian source under mean squared error distortion constraints, and focus on the three description problem. Inner and outer bounds for the rate region are derived, both of which can be represented as the intersection of ten half spaces with matching normal directions. Moreover, the gap between the inner and outer bounds is shown to be small. The inner bound relies on the rate region characterization of a lossless asymmetric multilevel diversity (MLD) coding problem treated in our earlier work, which is a natural generalization of the symmetric MLD coding problem previously considered by Roche et al. Different from symmetric MLD coding, superposition coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Equipped with this finding, and motivated by the connection between symmetric MD and symmetric MLD coding, in this work we consider asymmetric MD as a lossy version of the asymmetric MLD coding, which requires coding beyond simple superposition. An outer bound is also derived, which bears a geometric structure particularly suitable for comparison with the inner bound. Combining the inner and outer bounds provides an approximate characterization of the rate region for the asymmetric Gaussian three description problem.

We consider multiple description coding for the Gaussian source with K descriptions under the symmetric mean squared error distortion constraints. Inner and outer bounds for the achievable rate region are derived and carefully tailored, such that they can be compared conveniently. The inner bound is based on a generalization of the multilayer scheme previously proposed by Puri et al., through a more flexible binning method. The resulting achievable region has the same geometric structure as the rate region of the lossless multilevel diversity coding problem, which reveals a strong connection between them. The outer bound is derived by combining the bounding technique for the sum rate in our earlier work, together with the α-resolution method introduced by Yeung and Zhang. Comparison between the inner and outer bounds shows that the gap in between is upper bounded by some constants. Particularly for the three description problem, the bounds can be written explicitly, and both the inner and outer bounds can be represented by ten planes with matching normal directions, between which the pairwise difference is small.

In this paper we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.