We study the document exchange problem under multiple substring edits. A substring edit in a string $\mathbf{x}$ occurs when a substring $\mathbf{u}$ of $\mathbf{x}$ is replaced by an arbitrary string $\mathbf{v}$. The lengths of $\mathbf{u}$ and $\mathbf{v}$ are bounded from above by a fixed constant. Let $\mathbf{x}$ and $\mathbf{y}$ be two binary strings that differ by multiple substring edits. The aim of document exchange schemes is to construct an encoding of $\mathbf{x}$ with small length such that $\mathbf{x}$ can be recovered using $\mathbf{y}$ and the encoding. We construct a low-complexity document exchange scheme with encoding length of $4t\log n+o(\log n)$ bits, where $n$ is the length of the string $\mathbf{x}$. The best known scheme achieves an encoding length of $4t \log n+O(\log\log n)$ bits, but at a much higher computational complexity. Then, we investigate the average length of valid encodings for document exchange schemes with uniform strings $\mathbf{x}$ and develop a scheme with an expected encoding length of $(4t-1) \log n+o(\log n)$ bits. In this setting, prior works have only constructed schemes for a single substring edit.

In large-scale distributed storage systems, erasure coding is employed to ensure reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to significant storage savings without compromising reliability. Such adaptations, known ascode conversions, motivate the design ofconvertible codes, which enable efficient transformations between codes of different parameters. In this work, we study the setting in which λ codewords of an initial [nI=kI+rI,kI] MDS code are merged into a single codeword of a final [nF= λkI+rF,kF= λkI] MDS code. We begin by presenting three constructions that achieve optimalaccess cost, defined as the total number of disks accessed during the conversion process. The first two constructions apply when λ ≤rIand impose specific divisibility conditions onrIand the field sizeq. These schemes minimize both the per-symbol and the overall access cost. The third construction, which builds on a prior scheme by Kong, achieves minimal access cost while supporting arbitrary parameter regimes. All three constructions require field sizes that are linear in the final code length, and notably, the third construction achieves a field size that matches the lower bound implied by the MDS conjecture in almost all cases. In addition, we propose a construction that optimizes thebandwidth cost, defined as the total number of symbols transmitted during conversion. This scheme is a refinement of Maturana and Rashmi’s bandwidth-optimal construction based on the piggybacking framework, and achieves reduced sub-packetization.The code will be available at https://github.com/ZhilongNiu/SDMoMFE.

In large-scale distributed storage systems, erasure coding provides reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to storage savings, without compromising reliability. During such adaptations (also called code conversions), data encoded with multiple codewords of an initial [$n^{I}, k^{I}$] code are transformed into multiple codewords of a final$\left[n^{F}, k^{F}\right]$code. The convertible codes framework aims to design initial and final codes to enable resource-efficient conversions. In this paper, we study the scenario where$\lambda \geq 2$codewords of an initial$\left[n^{I}=k^{I}+r^{I}, k^{I}\right]$MDS code are merged into a single codeword of a final$\left[n^{F}=\lambda k^{I}+r^{F}, k^{F}=\lambda k^{I}\right]$MDS code. Some initial code symbols are retained in the final codeword, while others are newly generated. The access cost is the total number of symbols read or written during the conversion procedure to produce new symbols. In this paper, we present three convertible code constructions. The first two require$\lambda \leq r^{I}$and impose certain divisibility conditions on$r^{I}$and the field size$q$. However, they minimize the access cost incurred for generating each new symbol individually and for all symbols cumulatively. The third construction, a modification of an earlier construction by Kong, minimizes the cumulative access cost and works for all parameters. All the code constructions require field sizes linear in the block length of the final code and achieve the smallest known field sizes across MDS convertible codes in the literature.

Streaming codes are packet-level codes designed to ensure the timely recovery of lost packets. This paper focuses on streaming codes for multi-hop relay networks that guarantee the recovery of message packets within a delay of$\tau$time slots, even when a burst erasure affecting at most$b$packets occurs on each link. We first present a straightforward upper bound on the rate of burst-erasure-correcting streaming codes for multi-hop relay networks. The main contribution of this paper is a coding scheme that achieves rates arbitrarily close to this rate upper bound as the message size increases.

In this paper, we address the problem of secure distributed computation in scenarios where user data is not uniformly distributed, extending existing frameworks that assume uniformity, an assumption that is challenging to enforce in data for computation. Motivated by the pervasive reliance on single service providers for data storage and computation, we propose a privacy-preserving scheme that achieves informationtheoretic security guarantees for computing polynomials over non-uniform data distributions. Our framework builds upon the concept of perfect subset privacy and employs linear hashing techniques to transform non-uniform data into approximately uniform distributions, enabling robust and secure computation. We derive leakage bounds and demonstrate that information leakage of any subset of user data to untrusted service providers, i.e., not only to colluding workers but also (and more importantly) to the admin, remains negligible under the proposed scheme.

Streaming codes are codes designed to ensure erased packet recovery within a decoding-delay deadline. In streaming code literature, a sliding-window (SW) channel model is considered called the (a, b,w)-SW channel model. In the (a, b,w)-SW channel, within any window ofwtime slots, either a burst of ≤bconsecutive packets, or else ≤apackets at random can be erased. An (a, b,w,≤ ) streaming code is capable of recovering messages under a decoding-delay of τ time slots, from any erasure pattern produced by the (a, b,w)-SW channel. For any given (a, b,w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ =w− 1. Rate-optimal constructions of streaming codes for parameters of the form (a, b,w, τ =w− 1) are known, and these constructions require a field size that is quadratic in w in general. In this paper, we show that is possible to construct linear field size streaming codes for all {a, b,w} parameters, by sacrificing a little on either delay or rate. Moreover, we characterize the existence of binary, rate-optimal (a, b,w, τ =w−1) streaming codes constructed via the popular technique of diagonal embedding. Further, under a less-stringent decoding-delay requirement of τ = (w+b−a−1), it is shown that binary, rate-optimal streaming codes can be constructed for certain parameters. Streaming codes for a more general class of SW channels that allow unerased packets within a burst erasure are also investigated.

A typical setup in many machine learning scenarios involves a server that holds a model and a user that possesses data, and the challenge is to perform inference while safeguarding the privacy of both parties.Private Inferencehas been extensively explored in recent years, mainly from a cryptographic standpoint via techniques like homomorphic encryption and multiparty computation. These approaches often come with high computational overhead and may degrade the accuracy of the model. In our work, we take a different approach inspired by thePrivate Information Retrievalliterature. We view private inference as the task of retrieving inner products of parameter vectors with the data, a fundamental operation in many machine learning models. We introduce schemes that enable such retrieval of inner products for models withquantized(i.e., restricted to a finite set) weights; such models are extensively used in practice due to a wide range of benefits. In addition, our schemes uncover a fundamental tradeoff between user and server privacy. Our information-theoretic approach is applicable to a wide range of problems and robust in privacy guarantees for both the user and the server.

Minimum storage regenerating (MSR) codes are a class of maximum distance separable (MDS) array codes capable of repairing any single failed node by downloading the minimum amount of information from each of the helper nodes. However, MSR codes require large sub-packetization levels, which hinders their usefulness in practical settings. This led to the development of another class of MDS array codes called ε-MSR codes, for which the repair information downloaded from each helper node is at most a factor of (1 + ε) from the minimum amount for some ε > 0. The advantage of ε-MSR codes over MSR codes is their small sub-packetization levels. In previous constructions of epsilon-MSR codes, however, several specific nodes are required to participate in the repair of a failed node, which limits the performance of the code in cases where these nodes are not available. In this work, we present a construction of ε-MSR codes without this restriction. For a code withnnodes, out of whichkstore uncoded information, and for any numberdof helper nodes (k≤dn), the repair of a failed node can be done by contacting any set ofdsurviving nodes. Our construction utilizes group algebra techniques, and requires linear field size. We also generalize the construction to MDS array codes capable of repairinghfailed nodes using d helper nodes with a slightly sub-optimal download from each helper node, for allh≤n−kandk≤d≤n−hsimultaneously.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau $time slots, given that a single burst erasure of length at most b packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound, as message size increases.

Delegating large-scale computations to service providers is a common practice which raises privacy concerns. This paper studies information-theoretic privacy-preserving del-egation of data to a service provider, who may further delegate the computation to auxiliary worker nodes, in order to compute a polynomial over that data at a later point in time. We study techniques which are compatible with robust management of distributed computation systems, an area known as coded computing. Privacy in coded computing, however, has tradition-ally addressed the problem of colluding workers, and assumed that the server that administrates the computation is trusted. This viewpoint of privacy does not accurately reflect real-world privacy concerns, since normally, the service provider as a whole (i.e., the administrator and the worker nodes) form one cohesive entity which itself poses a privacy risk. This paper aims to shift the focus of privacy in coded computing to safeguarding the privacy of the user against the service provider as a whole, instead of merely against colluding workers inside the service provider. To this end, we leverage the recently defined notion of perfect subset privacy, which guarantees zero information leakage from all subsets of the data up to a certain size. Using known techniques from Reed-Muller decoding, we provide a scheme which enables polynomial computation with perfect subset privacy in straggler-free systems. Furthermore, by studying information super-sets in Reed-Muller codes, which may be of independent interest, we extend the previous scheme to tolerate straggling worker nodes inside the service provider.

Given a real dataset and a computation family, we wish to encode and store the dataset in a distributed system so that any computation from the family can be performed by accessing a small number of nodes. In this work, we focus on the families of linear computations where the coefficients are restricted to a finite set of real values. For two-valued computations, a recent work presented a scheme that gives good feasible points on the access-redundancy tradeoff. This scheme is based on binary covering codes having a certain closure property. In a follow-up work, this scheme was extended to all finite coefficient sets, using a new additive-combinatorics notion called coefficient complexity. In the present paper, we explore non-binary covering codes and develop schemes that outperform the state-of-the-art for some coefficient sets. We provide a more general coefficient complexity definition and show its applicability to the access- redundancy tradeoff.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau$time slots, given that a single burst erasure of length at most$b$packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound as message size increases.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations that are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), have gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where a smaller access parameter requires more redundancy in the system, and vice versa. In this paper, we study this tradeoff and provide several explicit low-access schemes for$\{\pm 1\}$quantized linear computations based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art for two-valued linear computations. We further show that the same storage scheme can be used to retrieve any linear combination with two distinct coefficients—regardless of what those coefficients are—with the same access parameter. This universality result is then extended to all possible quantizations with any number of values; while the storage remains identical, the access parameter increases according to a new additive-combinatorics property we call coefficient complexity. We then turn to study the coefficient complexity—we characterize the complexity of small sets of coefficients, provide bounds, and identify coefficient sets having the highest and lowest complexity. Interestingly, arithmetic progressions have the lowest possible complexity, and some geometric progressions have the highest possible complexity, the former being particularly attractive for its common use in uniform quantization.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size$(\tau +1)$time units, under a strict decoding-delay constraint$\tau $. The field size over which streaming codes are constructed is an important factor in determining the implementation complexity. The best-known explicit rate-optimal streaming code, which covers all$\{a,b,\tau \}$parameter choices, requires a field size of$q^{2}$, where$q \ge \tau +b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code over a field of size$q^{2}$, for prime power$q \ge \tau $. This is the smallest known field size for an explicit rate-optimal construction that takes into account all$\{a,b,\tau \}$parameters. We achieve this by modifying the non-explicit code construction due to Krishnan et al., without changing the field size. We also present a generalization of our construction, which results in streaming codes over further smaller fields by trading off code rate.

For a convolutional code in the presence of a symbol erasure channel, the information debt I(t) at time t provides a measure of the number of additional code symbols required to recover all message symbols up to time t. Information-debt-optimal streaming (iDOS) codes are convolutional codes which allow for the recovery of all message symbols up to t whenever I(t) turns zero under the following conditions; (i) information debt can be non-zero for at most τ consecutive time slots and (ii) information debt never increases beyond a particular threshold. The existence of periodically-time-varying iDOS codes are known for all parameters. In this paper, we address the problem of constructing explicit, time-invariant iDOS codes. We present an explicit time-invariant construction of iDOS codes for the unit memory (m = 1) case. It is also shown that a construction method for convolutional codes due to Almeida et al. leads to explicit time-invariant iDOS codes for all parameters. However, this general construction requires a larger field size than the first construction for the m = 1 case.

Streaming codes are codes designed to ensure erased packet recovery with a decoding-delay deadline. In streaming code literature, an (a, b, w) sliding-window (SW) channel model is considered, in which within any window of w time slots, either a burst of ≤ b packets, or else ≤ a random packets can be erased. An (a, b, w, τ) streaming code is a packet-level code capable of recovering messages under a decoding delay of τ time slots, from any erasure pattern produced by an (a, b, w)-SW channel. For any given (a, b, w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ = w−1. Rate-optimal constructions of streaming codes for any parameter tuple of the form (a, b, w, τ = w−1) are known in the literature. However, these constructions require a field size that is quadratic in w in general, and linear field size constructions are known only for a subset of {a, b, w} parameters. The current paper shows that it is possible to construct linear field size streaming codes for all {a, b, w} parameters, by sacrificing a little on either delay or rate. When the allowed delay is one more than the minimum, i. e., when τ = w, we construct linear field size rate-optimal streaming codes for all possible {a, b, w} parameters. This construction also leads to an O(w) field size (a, b, w, τ = w − 1) streaming code whose rate is close to the optimal rate. Additionally, we show that our construction can be modified to get binary streaming codes without too much loss in rate.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations which are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks, and reduces the overall communication in the system. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where smaller access parameter requires more redundancy in the system, and vice versa. In this paper we study this tradeoff, and provide several explicit code constructions based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art, and extend the framework to new families of computations.

In the context of an (n,k,m) convolutional code where k is the number of message symbols, n the number of code symbols and m the memory, Martinian [1] introduced the concept of information debt whose value at time t is the number of additional coded symbols needed to decode all prior message symbols. The same paper shows the existence of (n,k,m) convolutional codes that can recover all prior message symbols whenever the symbol-erasure pattern is such that the maximum time interval τ between successive returns to zero of the information debt function is at most m. The parameter τ also represents the worst-case delay in decoding a message symbol. In the present paper, we study (n,k,m) convolutional codes that possess the analogous property for the case τ > m whenever it is possible to do so. We will refer to such codes as information-debt-optimal streaming (iDOS) codes. We prove the existence of periodically time-varying iDOS codes for all possible {n,k,m,τ} parameters. We also show that m-MDS codes and Maximum Distance Profile convolutional codes are iDOS codes for certain parameter ranges. As a by-product of our existence result, the minimum memory needed for a particular class of streaming codes studied earlier in the literature, is determined.

Streaming codes are packet-level erasure-recovery codes which offer reliability in the presence of burst or random packet erasures, while operating under a strict decoding-delay constraint. The Gilbert-Elliott channel model is a commonly-accepted channel model for such settings. Most recent designs of streaming codes are designed for a sliding-window (SW) channel model that may be viewed as a tractable approximation to the GE channel. An (a, b, w)-SW channel, admits only those erasure patterns having the property that within any sliding window of w packet durations, there is either a burst of b packets that is erased, or else a random set of a packets. A streaming code operating over an (a, b, w)-SW channel should be capable of recovering from any admissible erasure pattern and must do so under a decoding-delay constraint τ, meaning that packet t must be decoded upon arrival of packet (t + τ). The focus in the literature has been on the construction of streaming codes that achieve an upper bound on code rate for such a channel and there exist rate-optimal code constructions for any (a, b, w)-SW channel with τ = (w − 1), and for the general case, the field-size requirement is quadratic in w. While a code designed for the case τ = (w − 1) can also be employed in settings where τ > (w − 1), we show in the present paper that it is possible to construct rate-optimal codes specifically for the regime τ ≥ (w − 1 + b − a) that have smaller field-size requirement and are hence simpler to implement. The constructions presented here are based on MDS and binary cyclic codes, corresponding respectively to a linear and binary field-size requirement.

Streaming codes represent a packet-level FEC scheme for achieving reliable, low-latency communication. In the literature on streaming codes, the commonly-assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-constrained, sliding-window (DCSW) channel model that can introduce either random or burst erasures. The known streaming codes that are rate optimal over the DCSW channel model are constructed by diagonally embedding a scalar block code across successive packets. These code constructions have field size that is quadratic in the delay parameter$\tau$and have a somewhat complex structure with an involved decoding procedure. This led to the introduction of simple streaming (SS) codes in which diagonal embedding is replaced by staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a burst of erasures and makes it possible to construct near-rate-optimal streaming codes using Maximum Distance Separable (MDS) code having linear field size. The present paper takes this development one step further, by retaining the staggered-diagonal feature, but permitting the placement of more than one code symbol from a given scalar codeword within each packet. These generalized, simple streaming codes allow us to improve upon the rate of SS codes, while retaining the simplicity of working with MDS codes. We characterize the maximum code rate of streaming codes under a constraint on the number of contiguous packets over which symbols of the underlying scalar code are dispersed. Such a constraint leads to simplified code construction and reduced-complexity decoding.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size ($\tau+1$) time units, under a strict decoding-delay constraint$\tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of$q^{2}$where$q\geq\tau+b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible$\{a, b,\tau\}$parameters, over a field of size$q^{2}$for prime power$q\geq \tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all$\{a, b, \tau\}$parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a $[{\tau}+1, {\tau}+1-{a}]$ Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from a arbitrary packet erasures, under a strict decoding delay constraint ${\tau}$. Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of a erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from ${a}\gt 1$ arbitrary packet erasures under a decoding delay ${\tau}$, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay ${r}\lt {\tau}$. We term these codes as $({a},{\tau},{r})$ locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters $\{{a},{\tau},{r}\}$. Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our (${a},{\tau}={a}({r}+1)-1,{r})$ LRSC construction provides the additional guarantee of recovery from the erasure of ${h}, 1\leq {h}\leq {a}$, packets, with delay ${h}({r}+1)-1$. The construction thus offers graceful degradation in decoding delay with increasing number of erasures. A full version of this paper is accessible at [1].

The Gilbert-Elliot (GE) channel is a commonlyaccepted model for packet erasures in networks. Streaming codes are a class of packet-level erasure codes designed to provide reliable communication over the GE channel. The design of a streaming code may be viewed as a two-step process. In the first, a more tractable, delay-constrained sliding window (DCSW) channel model is considered as a proxy to the GE channel. The streaming code is then designed to reliably recover from all erasures introduced by the DCSW channel model. Simulation is typically used to evaluate the performance of the streaming code over the original GE channel, as analytic performance evaluation is challenging. In the present paper, we take an important first step towards analytical performance evaluation. Recognizing that most, efficient constructions of a streaming code are based on the diagonal embedding or horizontal embedding of scalar block codes within a packet stream, this paper provides upper and lower bounds on the block-erasure probability of the underlying scalar block code when operated over the GE channel.A full version of this paper is accessible at [1].

An (a, b, τ) streaming code is a packet-level erasure code that can recover under a strict delay constraint of τ time units, from either a burst of b erasures or else of a random erasures, occurring within a sliding window of time duration w. While rate-optimal constructions of such streaming codes are available for all parameters {a, b, τ, w} in the literature, they require in most instances, a quadratic, O(τ2) field size. In this work, we make further progress towards field size reduction and present rate-optimal O(τ) field size streaming codes for two regimes: (i) gcd(b, τ + 1 - a) ≥ a (ii) τ + 1 a + b and b mod a ϵ 0, a - 1.

The coded MapReduce framework introduced in [1] gives a method to tradeoff extra computation for reduced communication, in-order to speedup operations for which communication is the bottleneck. In [2], it has been demonstrated that reducing the number of subfiles required in coded MapReduce at the cost of a slightly higher communication load is beneficial for certain problems. The placement delivery array (PDA), introduced in [3], is a structure used to develop coded caching schemes with small sub-packetization. In the present paper, we use PDA to come up with a method to construct coded MapReduce schemes which require smaller number of subfiles. This method gives a way to tradeoff between the number of subfiles and the communication required. We also address the problem of mitigating the impact of slow servers at the map phase on the reduce operations of normal servers.

The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi [1] who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with rephcated-server PIR. In the present paper, the construction of an (n, k) τ-server binary linear PIR code having parameters n =ℓΣi=0(mi), k = (mi) and τ = 2ℓfor any integer m ≥ ℓ ≥ 0 is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary. Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any τ = ∊ {2ℓ, 2ℓ− 1 | ℓ ∊ Z, ℓ ≥ 0} and any value of k, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with known short block length codes in [1]. For the particular case of τ = 3,4, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length n{k, τ) of a systematic PIR code. It follows from a result by Vardy and Yaakobi [2], that these codes also yield optimal, systematic primitive multi-set {n, k, τ)Bbatch codes for τ = 3,4. The PIR code constructions presented here also yield upper bounds on the generahzed Hamming weights of binary PRM codes.