This work presents an algorithmic framework that uses linear programming to construct addition-based Private Information Retrieval (AB-PIR) schemes, where retrieval is performed by downloading only linear combinations of message symbols with coefficients set to 0 or 1. The AB-PIR schemes generalize several existing capacity-achieving PIR schemes and are of practical interest because they use only addition operation-savoiding multiplication and other complex operations-and are compatible with any finite field, including binary. Our framework broadens the search space to include all feasible solutions and can be used to construct optimal AB-PIR schemes for the entire range of problem parameters, including the number of servers, the total number of messages, and the number of messages that need to be retrieved. The framework enables us to identify schemes that outperform the previously proposed PIR schemes in certain cases and, in other cases, achieve performance on par with the best-known AB-PIR solutions. Additionally, the schemes generated by our framework can be integrated into existing solutions for several related PIR scenarios, improving their overall performance.

This paper revisits the problem of multi-server Private Information Retrieval with Private Side Information (PIR-PSI). In this problem,$N$non-colluding servers store identical copies of$K$messages, each comprising$L$symbols from$\mathbb{F}_{q}$, and a user, who knows$M$of these messages, wants to retrieve one of the remaining$K-M$messages. The user's goal is to retrieve the desired message by downloading the minimum amount of information from the servers while revealing no information about the identities of the desired message and side information messages to any server. The capacity of PIR-PSI, defined as the maximum achievable download rate, was previously characterized for all$N,K$, and$M$when$L$and$q$are sufficiently large-specifically, growing exponentially with$K$, to ensure the divisibility of each message into$N^{K}$sub-packets and to guarantee the existence of an MDS code with its length and dimension being exponential in$K$. In this work, we propose a new capacity-achieving PIR-PSI scheme that is applicable to all N, K, M, L, and$q$where$N\geq M+1$and$N-1\vert L$. The proposed scheme operates with a sub-packetization level of$N-1$, independent of$K$, and works over any finite field without requiring an MDS code.

This paper presents new solutions for Private Information Retrieval (PIR) with side information. This problem is motivated by PIR settings in which a client has side information about the data held by the servers and would like to leverage this information in order to improve the download rate. The problem of PIR with side information has been the subject of several recent studies that presented achievability schemes as well as converses for both multi -server and single-server settings. However, the solutions for the multi-server settings adapted from the solutions for the single-server setting in a rather straightforward manner, relying on the concept of super-messages. Such solutions require an exponential degree of sub-packetization (in terms of the number of messages). This paper makes the following contributions. First, we revisit the PIR problem with side information and present a new approach to leverage side information in the context of PIR. The key idea of our approach is a randomized algorithm to determine the linear combinations of the sub-packets that need to be recovered from each server. In addition, our approach takes advantage of the fact that the identity of the side information messages does not need to be kept private, and, as a result, the information retrieval scheme does not need to be symmetric. Second, we present schemes for PIR with side information that achieve a higher rate than previously proposed solutions and require a significantly lower degree of sub-packetization (linear in the number of servers). Our scheme not only achieves the highest known download rate for the problem at hand but also invalidates a previously claimed converse bound on the maximum achievable download rate.

This paper introduces the problem of Private Information Retrieval with Reusable and Single-use Side Information (PIR-RSSI). In this problem, one or more remote servers store identical copies of a set of K messages, and there is a user that initially knows M of these messages, and wants to privately retrieve one other message from the set of K messages. The objective is to design a retrieval scheme in which the user downloads the minimum amount of information from the server(s) while the identity of the message wanted by the user and the identities of an M1-subset of the M messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining M2:=M−M1messages known by the user (referred to as single-use side information) do not need to be protected. The PIR-RSSI problem reduces to the classical Private Information Retrieval (PIR) problem when M1=M2= 0, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when M1≥ 1, M2= 0 or M1= 0, M2≥ 1, respectively. In this work, we focus on the single-server setting of the PIR-RSSI problem. We characterize the capacity of this setting for the cases of M1= 1, M2≥ 1 and M1≥ 1, M2= 1, where the capacity is defined as the maximum achievable download rate over all PIR-RSSI schemes. Our results show that for sufficiently small values of K, both the single-use and reusable side information messages can help in reducing the download cost; and for larger values of K, only the single-use side information messages can help in reducing the download cost.

This paper considers the problem of single-server Individually-Private Information Retrieval with side information (IPIR). In this problem, there is a remote server that stores a dataset of K messages, and there is a user that initially knows M of these messages, and wants to retrieve D other messages belonging to the dataset. The goal of the user is to retrieve the D desired messages by downloading the minimum amount of information from the server while revealing no information about whether an individual message is one of the D desired messages. In this work, we focus on linear IPIR schemes, i.e., the IPIR schemes in which the user downloads only linear combinations of the original messages from the server. We prove a converse bound on the download rate of any linear IPIR scheme for all K, D, M, and show the achievability of this bound for all K, D, M satisfying a certain divisibility condition. Our results characterize the linear capacity of IPIR, which is defined as the maximum achievable download rate over all linear IPIR schemes, for a wide range of values of K, D, M.

This paper introduces a generalization of the Private Information Retrieval with Side Information (PIR-SI) problem called Popularity-Aware PIR-SI (PA-PIR-SI). The PAPIR-SI problem includes one or more remote servers storing copies of a dataset of K messages, and a user who knows M out of K messages—the identities of which are unknown to the server—as a prior side information, and wishes to retrieve one of the remaining K M messages. The goal of the user is to minimize the amount of information they must download from the server while revealing no information about the identity of the desired message. In contrast to PIR-SI, in PA-PIR-SI, the dataset messages are not assumed to be equally popular. That is, given the M side information messages, each of the remaining K M messages is not necessarily equally likely to be the message desired by the user. In this work, we focus on the single-server setting of PA-PIR-SI, and establish lower and upper bounds on the capacity of this setting—defined as the maximum possible achievable download rate. Our upper bound holds for any message popularity profile, and is the same as the capacity of single-server PIR-SI. We prove the lower bound by presenting a PA-PIR-SI scheme which takes a novel probabilistic approach—carefully designed based on the popularity profile—to integrate two existing PIR-SI schemes. The rate of our scheme is strictly higher than that of the only existing PIR-SI scheme applicable to the PA-PIR-SI setting.

We introduce two generalizations to the paradigm of using Random Khatri-Rao Product (RKRP) codes for distributed matrix multiplication. We first introduce a class of codes called Sparse Random Khatri-Rao Product (SRKRP) codes which have sparse generator matrices. SRKRP codes result in lower encoding, computation and communication costs than RKRP codes when the input matrices are sparse, while they exhibit similar numerical stability to other state of the art schemes. We empirically study the relationship between the probability of the generator matrix (restricted to the set of non-stragglers) of a randomly chosen SRKRP code being rank deficient and various parameters of the coding scheme including the degree of sparsity of the generator matrix and the number of non-stragglers. Secondly, we show that if the master node can perform a very small number of matrix product computations in addition to the computations performed by the workers, the failure probability can be substantially improved.

This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation. The PLT problem includes one or more remote server(s) storing (identical copies of)$K$messages and a user who wants to compute$L$independent linear combinations of a$D$-subset of messages. The objective of the user is to perform the computation by downloading minimum possible amount of information from the server(s), while protecting the identities of the$D$messages required for the computation. In this work, we focus on the single-server setting of the PLT problem when the identities of the$D$messages required for the computation must be protected jointly. We consider two different models, depending on whether the coefficient matrix of the required$L$linear combinations generates a Maximum Distance Separable (MDS) code. We prove that the capacity for both models is given by$L/(K-D+L)$, where the capacity is defined as the supremum of all achievable download rates. Our converse proofs are based on linear-algebraic and information-theoretic arguments. For each model, we also present an achievability scheme that relies on MDS codes.

Abstract We propose two-stage adaptive pooling schemes, 2-STAP and 2-STAMP, for detecting COVID-19 using real-time reverse transcription quantitative polymerase chain reaction (RT-qPCR) test kits. Similar to the Tapestry scheme of Ghosh et al ., the proposed schemes leverage soft information from the RT-qPCR process about the total viral load in the pool. This is in contrast to conventional group testing schemes where the measurements are Boolean. The proposed schemes provide higher testing throughput than the popularly used Dorfman’s scheme. They also provide higher testing throughput, sensitivity and specificity than the state-of-the-art non-adaptive Tapestry scheme. The number of pipetting operations is lower than state-of-the-art non-adaptive pooling schemes, and is higher than that for the Dorfman’s scheme. The proposed schemes can work with substantially smaller group sizes than non-adaptive schemes and are simple to describe. Monte-Carlo simulations using the statistical model in the work of Ghosh et al . (Tapestry) show that 10 infected people in a population of size 961 can be identified with 70.86 tests on the average with a sensitivity of 99.50% and specificity of 99.62%. This is 13.5x, 4.24x, and 1.3x the testing throughput of individual testing, Dorfman’s testing, and the Tapestry scheme, respectively.

In this paper, we introduce the problem of Private Linear Transformation (PLT). This problem includes a single (or multiple) remote server(s) storing (identical copies of)$K$messages and a user that wants to compute$L$linear combinations of a$D$-subset of these messages by downloading the minimum amount of information from the server(s) while protecting the privacy of the entire set of$D$messages. This problem generalizes the private information retrieval and private linear computation problems. In this work, we focus on the single-server case. For the setting in which the coefficient matrix of the required$L$linear combinations generates a Maximum Distance Separable (MDS) code, we characterize the capacity for all parameters$K, D, L$, where the capacity is defined as the supremum of all achievable download rates. In addition, we present lower and/or upper bounds on the capacity for the settings with non-MDS coefficient matrices and the settings with a prior side information.

This paper considers the single-server Private Linear Transformation (PLT) problem when individual privacy is required. In this problem, there is a user that wishes to obtain$L$linear combinations of a D-subset of messages belonging to a dataset of$K$messages stored on a single server. The goal is to minimize the download cost while keeping the identity of every message required for the computation individually private. We focus on the setting in which the matrix of coefficients pertaining to the required linear combinations is the generator matrix of a maximum distance separable code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain divisibility conditions. In addition, we present lower bounds on the capacity of the settings in which the user has a prior side information about a subset of messages.

This paper considers the problem of single-server Individually-Private Information Retrieval (IPIR). In this problem, a user wants to retrieve D messages belonging to a dataset of K messages stored on a single server. Initially, the user knows M other messages belonging to the dataset as side information, where the identities of these M messages are unknown to the server. The goal is to minimize the total amount of information that the user must download from the server while keeping the identity of each of the D desired messages individually private, i.e., the identity of every individual message wanted by the user must be protected. The capacity of IPIR, which is defined as the supremum of all achievable download rates, was previously characterized for D = 2, M = 1. However, the capacity was left open for all other values of D, M. In this work, we present a technique for the proof of converse, based on a novel combinatorial approach. Using this technique, we establish an upper bound on the capacity of IPIR for D = 2, M = 2. For this setting, we also propose a new IPIR scheme—based on a probabilistic partitioning of the messages, that achieves the capacity upper bound. We believe that our approach can be employed for proving the converse and designing optimal schemes for the general cases of the problem.

We introduce a class of codes, called Squeezed Random Khatri-Rao Product (RKRP) codes, for coded matrix multiplication when each worker node can perform multiple submatrix products. The proposed codes are a generalization of RKRP codes in [1] and are built on the idea of squeezed polynomial codes in [2]. We show that squeezed RKRP codes are maximum distance separable with probability 1. They have the same communication cost as that of squeezed polynomial codes while offering better numerical stability.

We study the role of coded side information in single-server Private Information Retrieval (PIR). An instance of the single-server PIR problem includes a server that stores a database of K independently and uniformly distributed messages, and a user who wants to retrieve one of these messages from the server. We consider settings in which the user initially has access to a coded side information which includes a linear combination of a subset of M messages in the database. We assume that the identities of the M messages that form the support set of the coded side information as well as the coding coefficients are initially unknown to the server. We consider two different models, depending on whether the support set of the coded side information includes the requested message or not. We also consider the following two privacy requirements: (i) the identities of both the demand and the support set of the coded side information need to be protected, or (ii) only the identity of the demand needs to be protected. For each model and for each of the privacy requirements, we consider the problem of designing a protocol for generating the user's query and the server's answer that enables the user to decode the message they need while satisfying the privacy requirement. We characterize the (scalar-linear) capacity of each setting, defined as the ratio of the number of information bits in a message to the minimum number of information bits downloaded from the server over all (scalar-linear) protocols that satisfy the privacy condition. Our converse proofs rely on new information-theoretic arguments-tailored to the setting of single-server PIR and different from the commonly-used techniques in multi-server PIR settings. We also present novel capacity-achieving scalar-linear protocols for each of the settings being considered.

This paper considers the problem of single-server Private Computation (PC) in the presence of Side Information (SI). In this problem, there is a server that stores K i.i.d. messages, and a user who has a subset of M uncoded messages or a coded linear combination of them as side information, where the identities of these messages are unknown to the server. The user wants to privately compute a linear combination of a subset of D other messages by downloading information from the server, where the identities of these messages must be kept private individually or jointly. For each setting, we define the capacity as the supremum of all achievable download rates.We characterize the capacity of both PC with coded and un-coded SI when individual privacy is required, for all K, M, D. Our results indicate that both settings have the same capacity. In addition, we establish a non-trivial lower bound on the capacity of PC with coded SI when joint privacy is required, for a range of parameters K, M, D. This lower bound is the same as the lower bound we previously established on the capacity of PC with uncoded SI when joint privacy is required.

We propose two coding schemes for distributed matrix multiplication in the presence of stragglers. These coding schemes are adaptations of Luby Transform (LT) codes and Raptor codes to distributed matrix multiplication and are termedFactored LT (FLT) codesandFactored Raptor (FRT) codes. We show that all nodes in the Tanner graph of a randomly sampled code have a tree-like neighborhood with high probability. This ensures that the density evolution analysis gives a reasonable estimate of the average recovery threshold of FLT codes. The recovery threshold of the proposed FLT codes is asymptotically optimal when the output degree distribution is Soliton. Empirically, we show that FRT codes have an excellent recovery threshold while the number of worker nodes is moderately large. In addition, using Azuma–Hoeffding inequality, we derive concentration results to show that the recovery threshold of a randomly chosen FLT code is close to the ensemble average. FLT and FRT codes have better recovery thresholds when compared to Product codes and they are expected to have better numerical stability when compared to Polynomial codes, while they can also be decoded with a low-complexity decoding algorithm. Finally, the proposed codes are better matched to the practically important case of sparse matrix-matrix multiplication as compared to many previous schemes.

This work considers the distributed multivariate polynomial evaluation (DMPE) problem using a master-worker framework, which was originally considered by Yu et al., where Lagrange Coded Computing (LCC) was proposed as a coded computation scheme to provide resilience against stragglers for the DMPE problem. In this work, we propose a variant of the LCC scheme, termed Product Lagrange Coded Computing (PLCC), by combining ideas from classical product codes and LCC. The main advantage of PLCC is that they are more numerically stable than LCC; however, their resilience to stragglers is sub-optimal.

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of M messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is K - M messages, and in the second scenario it is [K/(M + 1)] messages, which should be compared to K messages-the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

We consider a multi-user variant of the private information retrieval problem described as follows. Suppose there are D users, each of which wants to privately retrieve a distinct message from a server with the help of a trusted agent. We assume that the agent has a subset of M messages whose indices are unknown to the server. The goal of the agent is to collectively retrieve the users' requests from the server. For this problem, we introduce the notion of individual-privacy - the agent is required to protect the privacy only for each individual user (but may leak some correlations among user requests). We refer to this problem as Individually-Private Information Retrieval with Side Information (IPIR-SI).We first establish a lower bound on the capacity, which is defined as the maximum achievable download rate, of the IPIR-SI problem by presenting a novel achievability protocol. Next, we characterize the capacity of IPIR-SI problem for M = 1 and D = 2. In the process of characterizing the capacity for arbitrary M and D we present a novel combinatorial conjecture, that may be of independent interest.

We study the problem of single-server single-message Private Information Retrieval with Private Coded Side Information (PIR-PCSI). In this problem, there is a server that stores a database, and a user who knows a random linear combination of a random subset of messages in the database. The number of messages contributing to the user's side information is known to the server a priori, whereas the indices and the coefficients of these messages are unknown to the server a priori. The user wants to retrieve a message from the server, while protecting the identities of both the demand message and the side information messages. Depending on whether the demand is part of the coded side information or not, we consider two different models for the problem. For the model in which the demand does not contribute to the side information, we prove a lower bound on the minimum download cost for all (linear and non-linear) PIR schemes; and for the model wherein the demand is one of the messages contributing to the side information, we prove a lower bound for all scalar-linear PIR protocols. In addition, we propose novel PIR protocols that achieve these lower bounds.

This paper considers the problem of single-server Private Computation wit Side Information (PC-SI). In this problem, there is a user that initially has a subset of M messages from a database stored on a single server, where the identities of the side information messages are initially unknown to the server. The user wishes to compute a linear combination of a subset of D messages (disjoint from the set of side information messages) while protecting the identities of the messages in the demanded linear combination. The objective of the user is to minimize the download cost, which is defined as the total amount of information that the user downloads from the server.We establish a lower bound on the capacity of the PC-SI problem, where the capacity is defined as the supremum of all achievable download rates. The proof relies on a novel achievability scheme which combines together the ideas of the interference alignment and the Partition and Code scheme previously introduced for private information retrieval with side information. In addition, for the case of M = 1 and D = 2, we prove the tightness of the rate achievable by the proposed scheme, when we restrict ourselves to the scalar-linear PC-SI schemes. The proof of converse is based on a combination of new algebraic and information-theoretic arguments.

In many practical settings, the user needs to retrieve information messages from a server in a periodic manner, over multiple rounds of communication. The messages are retrieved one at a time and the identity of future requests are not known to the server. In this paper, we focus on the private information retrieval protocols that ensure that the identities of all the messages retrieved from the server are protected. This scenario can occur in practical settings such as periodic content download from text and multimedia repositories. We refer to this problem of minimizing the rate of data download as online private information retrieval problem.Following the previous line of work by Kadhe et al. we assume that the user knows a subset of M messages in the database as side information. The identities of these M messages are initially unknown to the server. Focusing on scalar-linear settings, we characterize the per-round capacity, i.e., the maximum achievable download rate at each round. In particular, we show that for the setting with K messages stored at the server, the per-round capacity of the scalar-linear setting is C1= (M + 1)/K for round i = 1 and Ci= (2i -1(M + 1))/KM for round i ≥ 2, provided that K/(M + 1) is a power of 2. The key idea≥of our achievability scheme is to combine the data downloaded during the current round and the previous rounds with the original side information messages and use the resulting data as side information for the subsequent rounds.

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRCs), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in cooperative locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols.In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.

This paper considers the problem of Quantitative Group Testing (QGT). Consider a set of N items among which K items are defective. The QGT problem is to identify (all or a sufficiently large fraction of) the defective items, where the result of a test reveals the number of defective items in the tested group. In this work, we propose a non-adaptive QGT scheme using sparse graph codes over bi-regular bipartite graphs and binary t-error-correcting BCH codes. The proposed scheme provides exact recovery with probabilistic guarantee, i.e. recovers all the defective items with high probability. In particular, we show that for the sub-linear regime where K vanishes as K, N → ∞, the proposed scheme requires at most m ≈ 1.19K log2(4.74 N/K) tests to recover all the defective items with probability approaching one as K, N → ∞. This bound can be achieved by t = 2. The testing and recovery algorithms of the proposed scheme for any t ≤ 4 have the computational complexity of O(K log2N/K) and O(K log N/K), respectively. Our simulation results also show that the proposed scheme significantly outperforms a non-adaptive semi-quantitative group testing scheme recently proposed by Abdalla et al. in terms of the required number of tests for identifying all the defective items with high probability.

We show that Polynomial codes (and some related codes) used for distributed matrix multiplication are interleaved Generalized Reed-Solomon codes and hence, can be collaboratively decoded. We consider a fault-tolerant setup where t out of N workers return erroneous values. For an additive random Gaussian error model, we show that for any t ≤ N - K - 1, where K is the effective dimension of the code, all errors can be corrected with probability 1 while the decoding complexity is O(( L/L+1)4(N - K)4+ LN) for any L ≥ N - K - 1.

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results.

Variable-length (VL) coding sends an initial codeword followed by subsequent transmissions of incremental redundancy (IR) sent when the decoder indicates through feedback that it has not yet identified a reliable codeword. VL coding is a staple of modern communication to handle fading, and recent theoretical analysis and applications have demonstrated its value on non-fading channels for applications that require short blocklengths. To maximize throughput in a VL setting, the length of each IR transmission should be optimized. Sequential differential optimization (SDO) computes transmission lengths that optimize throughput by minimizing average blocklength. SDO produces a family of solutions that each maximize throughput for a specified maximum number of transmissions. This paper considers the average number of feedback transmissions per message as an alternative metric for the cost of the feedback resource. A Lagrangian approach provides a new SDO solution that jointly minimizes both the average blocklength and the average number of feedback transmissions associated with a message. The mapping of real-valued SDO solutions to the necessarily integer transmission lengths is also addressed.

As sensing and instrumentation play an increasingly important role in systems controlled over wired and wireless networks, the need to better understand delay-sensitive communication becomes a prime issue. Along these lines, this article studies the operation of data links that employ incremental redundancy as a practical means to protect information from the effects of unreliable channels. Specifically, this work extends a powerful methodology termed sequential differential optimization to choose near-optimal block sizes for hybrid ARQ over erasure channels. Furthermore, results show that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when analyzing throughput. Overall, block size selection is motivated by normal approximations on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid ARQ and coding, offers a pragmatic means to select code rates and blocklengths for incremental redundancy.

This paper considers the problem of cooperative data exchange with selfish users. In this setting, each user has a subset of packets in the ground set$X$, and wants all other packets in$X$. The users can exchange coded combinations of their packets over a lossless broadcast channel, and monetary transactions are allowed between any pair of users. We define the utility of each user as the sum of two functions: (i) the difference between the total payment received by the user and the total transmission rate of the user, and (ii) the difference between the total number of required packets by the user and the total payment made by the user. A rate-vector and payment-matrix pair$(r,p)$is said to stabilize the grand coalition (i.e., the set of all users) if$(r,p)$is Pareto optimal over all minor coalitions (i.e., all proper subsets of users who collectively know all packets in$X$). Our goal is to design a stabilizing rate-payment pair with minimum sum-rate and minimum sum-payment for any given problem instance. In this work, we show that such a solution always exists, and we propose two algorithms to find such a solution. Moreover, we show that both algorithms maximize the sum utility of all users, while one also maximizes the minimum utility among all users.

This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of n ≥ 2 coins of total weight d (for a known integer d), where the weight of each coin is an unknown integer in the range of {0, 1, ..., k} (for a known integer k ≥ 1), the goal is to determine the weight of each coin by weighing subsets of coins in a spring scale. The problem is to devise a weighing strategy that minimizes the average number of weighings over all possible weight configurations. For d = k = 1, an adaptive bisecting weighing strategy is known to be optimal. However, even the simplest non-trivial case of the problem, i.e., d = k = 2, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. Our analysis shows that the proposed strategy requires about 1.365log2n-0.5 weighings on average. As n grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about 31.75% less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about 8.16% extra number of weighings on average.

This paper considers the problem of single-server single-message private information retrieval with coded side information (PIR-CSI). In this problem, there is a server storing a database, and a user which knows a linear combination of a subset of messages in the database as a side information. The number of messages contributing to the side information is known to the server, but the indices and the coefficients of these messages are unknown to the server. The user wishes to download a message from the server privately, i.e., without revealing which message it is requesting, while minimizing the download cost. In this work, we consider two different settings for the PIR-CSI problem depending on the demanded message being or not being one of the messages contributing to the side information. For each setting, we prove an upper bound on the maximum download rate as a function of the size of the database and the size of the side information, and propose a protocol that achieves the rate upper-bound.

This paper considers the problem of approximating the failure frequency of large-scale composite k-terminal reliability systems. In such systems, the nodes (k of which are terminals) are connected through components, which are subject to random failure and repair processes. At any time, a system failure occurs if the surviving system fails to connect all the k terminals together. We assume that each component's up times and down times follow statistically independent stationary random processes, and these processes are statistically independent across the components. In this setting, the exact computation of failure frequency is known to be computationally intractable (NP-hard). In this paper, we present an algorithm to approximate the failure frequency for any given multiplicative error factor that runs in polynomial time in the number of (minimal) cutsets. Moreover, for the special case of all-terminal reliability systems, i.e., where all the nodes are terminals, we propose an algorithm for approximating the failure frequency within an arbitrary multiplicative error that runs in polynomial time in the number of nodes (which can be much smaller than the number of cutsets). Our simulation results confirm that the proposed method is much faster and more accurate than the standard Monte Carlo simulation technique for approximating the failure frequency.

This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given m χ n binary matrix M, the GM-MDS conjecture, due to Dau et al., states that if M satisfies the so-called MDS condition, then for any field F of size q ≥ n + m - 1, there exists an [n, m]qMDS code whose generator matrix G, with entries in F, fits M (i.e., M is the support matrix of G). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by Yan et al. and Dau et al., that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if M satisfies the MDS condition, then the determinant of a transformation matrix T, such that TV fits M, is not identically zero, where V is a Vandermonde matrix with distinct parameters. In this work, we generalize the TM-MDS conjecture, and present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows (m) of M is upper bounded by 5. For this class of special cases of M where the only additional constraint is on m, only cases with m4.

This paper considers two generalizations of the cooperative data exchange problem, referred to as the successive local omniscience (SLO) and the successive global omniscience (SGO). The users are divided into ℓ nested sub-groups. Each user initially knows a subset of packets in a ground set X of size k, and all users wish to learn all packets in X. The users exchange their packets by broadcasting coded or uncoded packets. In SLO or SGO, in the lth (1≤ l ≤ ℓ) round of transmissions, the lth smallest ub-group of users need to learn all packets they collectively hold or all packets in X, respectively. The problem is to find the minimum sum-rate (i.e., the total transmission rate by all users) for each round, subject to minimizing the sum-rate for the previous round. To solve this problem, we use a linear-programming approach. For the cases in which the packets are randomly distributed among users, we construct a system of linear equations whose solution characterizes the minimum sum-rate for each round with high probability as k tends to infinity. Moreover, for the special case of two nested groups, we derive closed-form expressions, which hold with high probability as k tends to infinity, for the minimum sum-rate for each round.

This paper considers the problem of cooperative data exchange with different client priority classes. In this problem, each client initially knows a subset of packets in the ground set X of size K, and all clients wish to learn all packets in X. The clients exchange packets by broadcasting coded combinations of their packets. The primary objective is to satisfy all high-priority clients in the first round of transmissions with minimum sum-rate, and the secondary objective is to satisfy low-priority clients in the second round of transmissions with minimum sum-rate, subject to minimizing the sum-rate in the first round. For any arbitrary problem instance, we provide a linear programming-based approach to find the minimum sum-rate in each round. Moreover, for the case in which the packets are randomly distributed among clients, we derive a closed-form expression for the minimum sum-rate in each round, which holds with probability approaching 1 as K tends to infinity.

In this work, we consider the problem of designing efficient feedback-based scheduling policies for chunked codes (CC) over single-path (line) networks with stochastic (queuing) delay. The state of the art in such policies are random push (RP) and local-rarest-first (LRF), which outperform the original policy of CC, namely the uniformly-at-random policy, in terms of the expected throughput even without any knowledge about the delay model. To our knowledge, however, this work is the first attempt to discover how much better one policy can do in an ideal case with perfect feedback when the model of delay is perfectly known. Towards this goal, we propose a new policy, referred to as transmitted-innovation-maximizer (TIM), based on the expected number of innovative packet transmissions at each transmitting node of the network by the next transmission time given the feedback information from the receiving node about the received packets. Our simulations show that TIM provides significantly larger (tighter) lower bounds on the maximum expected throughput (compared to the tightest existing bounds provided by LRF and RP), and thus it can be considered as the newest benchmark in this emerging line of research.

In this paper, we study the coding delay and the average coding delay of random linear network codes (dense codes) over line networks with deterministic regular and Poisson transmission schedules. We consider both lossless networks and networks with Bernoulli losses. The upper bounds derived in this paper, which are in some cases more general, and in some other cases tighter, than the existing bounds, provide a more clear picture of the speed of convergence of dense codes to the min-cut capacity of line networks.

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressed sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimensionn). The asymptotic analysis predicts the fraction of unverified signal elements at each iterationlin the asymptotic regime wheren→∞. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of nontrivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function ofl. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values ofn. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is more accurate and simpler to implement.

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressive sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension n). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration ℓ in the asymptotic regime where n → ∞. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of non-trivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of ℓ. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of n. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate.

To lower the complexity of network codes over packet line networks with arbitrary schedules, chunked codes (CC) and overlapped chunked codes (OCC) were proposed in earlier works. These codes have been previously analyzed for relatively large chunks. In this paper, we prove that for smaller chunks, CC and OCC asymptotically approach the capacity with an arbitrarily small but non-zero constant gap. We also show that unlike the case for large chunks, the larger is the overlap size, the better would be the tradeoff between the speed of convergence and the message or packet error rate. This implies that OCC are superior to CC for shorter chunks. Simulations consistent with the theoretical results are also presented, suggesting great potential for the application of OCC for multimedia transmission over packet networks.