In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on that trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions.

Recent advances in the flash memory technology call for more efficient error-correction codes (ECCs) than the conventional, yet very popular, ones such as BCH codes. The ability to make multiple voltage reads allows one to estimate soft values at the time of decoding, which in turn makes soft-decision ECCs such as LDPC codes a suitable candidate for implementation in flash memories. On the other hand, fully utilizing the potential of soft decision based codes demands higher precision memory sensing, which introduces a trade-off between the read latency and the error probability. In this paper, we explore and compares two approaches to optimize the positioning as well as the number of read (word-line) voltages for a specified program/erase (PE) cycle.In the first approach, we aim for selecting those read thresholds that maximize the mutual information (MMI) of the equivalent discrete memoryless channel. By utilizing conventional optimization methods such as the gradient descent (GD), we are able to find the optimal read locations for any number of read probes. Our simulation results show that ~20 reads are effective. Next, we redesign our optimization problem to take the LDPC code structure into account. To do so, we use discretized density evolution (DDE) as a proxy for bit error rate (BER), which serves as our cost function in the GD search. To overcome the problem of local minima, we propose a two-step optimization: MMI for coarse optimization, followed by DDE for fine optimization. Simulation results confirm the effectiveness of this method.1

Successive-cancellation list (SCL) decoding is a widely used and studied decoding algorithm for polar codes. For short blocklengths, empirical evidence shows that SCL decoding with moderate list sizes (say,$L \leq 32$) closely matches the performance of maximum-likelihood (ML) decoding. Hashemi et al. proved that on the binary erasure channel (BEC), SCL decoding actually coincides with ML decoding for list sizes$L \geq 2^{\gamma}$, where$\gamma$is a new parameter we call the mixing factor. Loosely speaking, the mixing factor counts the number of information bits mixed-in among the frozen bits; more precisely$\gamma=\vert\{i\in \mathcal{F}^{c}:i\leq \max\{\mathcal{F}\}\}\vert$, where$\mathcal{F}\subset [n]$denotes the set of frozen indices. Herein, we extend the aforementioned result of Hashemi et al. from the BEC to arbitrary binary-input memoryless symmetric channels. Our proof is based on capturing all$2^{\gamma}$decoding paths that correspond to the$\gamma$information bits appearing before the last frozen bit, and then finding the most-likely extension for each of these paths efficiently using a nearest coset decoding algorithm introduced herein. Furthermore, we present a hybrid successive-cancellation list (H -SCL) decoding algorithm, which is a hybrid between conventional SCL decoding and nearest coset decoding. We believe that the hybrid algorithm can outperform the conventional SCL decoder with lower decoding complexity.

This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements$P$that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is$O\left(N^{1-1/\mu}+ \frac{N}{P}\log_{2}\log_{2}\frac{N}{P}\right)$, where$N$is the block length of the code and$\mu$is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where$P=\frac{N}{2}$, the latency of SSC decoding is$O\left(N^{1-1/\mu}\right)$, which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where$P=1$, the latency of SSC decoding scales as$O(N\, \log_{2}\log_{2}N)$. The multiplicative constant is also calculated: we show that the latency of SSC decoding when$P=1$is given by$(2+o(1))N\, \log_{2}\log_{2}N$. Third, in a semi-parallel implementation, the smallest$P$that gives the same latency as that of the fully-parallel implementation is$P=N^{1/\mu}$. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

We present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distributions that arise in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, we can compute the entire weight distribution of certain polar cosets in time$O(n^{2})$. Any polar code can be represented as a disjoint union of such cosets; moreover, this representation extends to polar codes with dynamically frozen bits. This implies that our methods can be also used to compute the weight distribution of polar codes with CRC precoding, of pol-arization-adjusted convolutional (PAC) codes and, in fact, general linear codes. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To reduce the exponential complexity of our algorithm, we make use of the fact that polar codes have a large automorphism group, which includes the lower-triangular affine group LTA$(m,2)$. We prove that LTA$(m,2)$acts transitively on certain subsets of polar codes, thereby drastically reducing the number of polar cosets we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of any polar code of length up to$n=128$.

The problem of channel polarization for an arbitrary sequence$\{W_{i}\}_{i=0}^{n-1}$of$n$independent channels, referred to as a nonstationary sequence of channels, is considered. Also, each of the channels is used only once for communication. We consider a general framework for polarization of non-stationary channels and aim at optimizing the framework toward obtaining the best polarization. This framework includes permuting channels before Arıkan's pairwise channel combining operations are applied at each polarization level and skipping certain combining operations. We define an explicit optimization problem with the objective of finding the best permutation and indices of skipped operations in order to minimize a certain measure of polarization in one-level polarization. We then provide a complete solution to this optimization problem in the case of non-stationary binary erasure channels (BECs). We also propose a greedy method for polarizing non-stationary BECs, based on our solution for one-level polarization. Numerical results confirm the superiority of our method, in terms of various performance metrics, for constructing polar codes in certain non-stationary settings compared to prior work.

We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε > 0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ = 2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2×2 kernel) on the BEC is μ = 3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there existl×lbinary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ(l) that tends to the optimal value of 2 aslgrows. We furthermore characterize precisely how largelneeds to be as a function of the gap between μ(l) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(nlogn).

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correctingonly twodeletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct${d}$deletions in a codeword of length${n}$, successive-cancellation decoding is run separately for each of the$\binom {n}{d}$possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in${m} = \log _{2} {n}$decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most$\binom {d+2}{2}$scenarios at each node, and the overall decoding complexity is only${O}\bigl ({d}^{3} {n} \log {n}\bigr)$, which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions${d}$is small,i.e.${d}={o}({n})$. We also conjecture the strong polarization for when${d}={O}(1)$and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions.

Successive-cancellation decoding has gained much renewed interest since the advent of polar coding a decade ago. For polar codes, successive-cancellation decoding can be accomplished in time O(n log n). However, the complexity of successive-cancellation decoding for other families of codes remains largely unexplored. Herein, we prove that successive-cancellation decoding of general binary linear codes is NP-hard. In order to establish this result, we reduce from maximum-likelihood decoding of linear codes, a well-known NP-complete problem. Unlike maximum-likelihood decoding, however, the successive-cancellation decoding problem depends on the choice of a generator matrix. Thus we further strengthen our result by showing that there exist codes for which successive-cancellation decoding remains hard for every possible choice of the generator matrix. On the other hand, we also observe that polynomial-time successive-cancellation decoding can be extended from polar codes to many other linear codes. Finally, we show that every binary linear code can be encoded as a polar code with dynamically frozen bits. This approach makes it possible to use list-decoding of polar codes to approximate the maximum-likelihood decoding performance of arbitrary codes.

Polar coding gives rise to the first explicit family of codes that provably achieve capacity with efficient encoding and decoding for a wide range of channels. However, its performance at short block lengths under standard successive cancellation decoding is far from optimal. A well-known way to improve the performance of polar codes at short block lengths is CRC precoding followed by successive-cancellation list decoding. This approach, along with various refinements thereof, has remained the state of the art in polar coding since it was first introduced in 2011. Last year, Arıkan presented a new polar coding scheme, which he called polarization-adjusted convolutional (PAC) codes. Such PAC codes provide another dramatic improvement in performance as compared to CRC-aided list decoding. These codes are based primarily upon the following main ideas: replacing CRC precoding with convolutional precoding (under appropriate rate profiling) and replacing list decoding by sequential decoding. Arıkan's simulation results show that PAC codes, resulting from the combination of these ideas, are quite close to finite-length lower bounds on the performance of any code under ML decoding.One of our main goals in this paper is to answer the following question: is sequential decoding essential for the superior performance of PAC codes? We show that similar performance can be achieved using list decoding when the list size L is moderately large (say, L ≥ 128). List decoding has distinct advantages over sequential decoding in certain scenarios such as low-SNR regimes or situations where the worst-case complexity/latency is the primary constraint. Another objective is to provide some insights into the remarkable performance of PAC codes. We first observe that both sequential decoding and list decoding of PAC codes closely match ML decoding thereof. We then estimate the number of low weight codewords in PAC codes, and use these estimates to approximate the union bound on their performance under ML decoding. These results indicate that PAC codes are superior to polar codes and Reed-Muller codes, and suggest that the goal of rate-profiling may be to optimize the weight distribution at low weights.

Polar coding has found its way into many realms in communications and information theory. In most implementation setups, they are accompanied with the list successive cancellation (LSC) decoding algorithm which is shown to provide a superior error performance compared to the original successive cancellation (SC) decoding method. While the SC decoding is fairly well-studied, the exact math behind LSC's superior performance still remains to be of mystery. Multiple techniques have been proposed to further improve the LSC's error performance or to reduce its computational complexity, which are usually motivated by heuristic reasons and shown through numerical simulations. Most notable example is the CRC-aided LSC, which drastically improves the LSC's performance by concatenating the polar code with some high-rate cyclic redundancy check (CRC) codes.In this paper, we present polar codes that are concatenated with an underlying high-rate convolutional code, which are shown to have superior performances over CRC-aided LSC. We also present a computationally-efficient decoding algorithm for these codes which resembles the techniques used in the Viterbi algorithm, and hence is called the convolutional decoding algorithm. To do this, we revisit the error analysis of the original SC decoding along with the concept of Arıkan's helper genie. We address some shortcomings of the CRC-aided LSC and discuss how to turn around them by emulating a convolutional code instead of a CRC code. Contrary to CRC codes, most of the convolutional codes are not a proper choice for concatenation with polar codes. We introduce the bucketing algorithm to construct suitable punctured convolutional codes for this purpose. The proposed framework can accommodate any such underlying convolutional code, which allows one to search for the optimal convolutional code based on their design parameters.

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on this trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. Using this approach, we obtain a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length.

Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the scaling exponent μ. It is well known that the optimal scaling exponent, achieved by random binary codes, is μ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is μ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent μ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel. Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ≤ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μℓtransforms an underlying BEC into ℓ bit-channels W1, W2>,..., Wℓ. The erasure probabilities of W1, W2>,..., Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent μ(Kℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing Kℓto that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K32and K64. In order to evaluate the polarization behavior of K32and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that μ(K64) <; 2.97.

In this paper, we propose a polar coding scheme for binary deletion channels. We also present an implementation of low-complexity polar SC decoder for deletion channels. The modified decoding algorithm requires only O(d2nlogn) computational complexity, where d and n respectively denote the number of deletions and the code-length. This is a huge improvement over naive implementation of the SC decoder for channels with deletion with O(nd+1logn) computation complexity that was recently proposed by Thomas et al. in [21], and is based on running individual instances of SC decoder for every deletion pattern while treating the deleted symbols as erasures. We also prove polarization theorems for the polar bit-channels in presence of deletions when d = o(n), which implies that our coding scheme is capable of achieving the symmetric information rate for this concatenated scheme with diminishing error probabilities as n becomes large. The same framework, in both theory and implementation, is also applicable to channels formed as a concatenation between binary discrete memoryless channels and the d-deletion channel, which marks our coding scheme as the first family of practical codes that is capable of decoding noisy channels with deletions at the optimal code rate.

We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε2+δ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).

Polar codes provably achieve the capacity of memoryless symmetric channels with low encoding and decoding complexity. Nonetheless, for short and moderate blocklengths, polar codes fail to deliver competitive performance under successive cancellation decoding. Consequently, much effort has been devoted to improving the performance of polar codes, either through enhanced decoding algorithms or by modifying the code structure, or both. CRC-aided list decoding of polar codes is the most successful approach along this line of research. However, list decoding requires following L decoding paths, which leads to a significant increase in decoding complexity if L is large. As noted by Arikan shortly after the invention of polar codes, their performance could be improved dramatically if we had a genie that intervenes in the successive cancellation decoding process only a few times to reverse incorrect decisions on information bits. In fact, the Tal-Vardy list-decoding algorithm for polar codes can be regarded as an attempt to implement such a genie. Herein, we introduce an alternative implementation of Arikan's genie, which has much lower complexity than list decoding. Our approach is based on precoding some of the information bits with a short convolutional code that provides local error- correction capability at the expense of a small rate loss. This structure allows the successive cancellation polar decoder to verify its output by running it through a Viterbi decoder for the convolutional code. In contrast to conventional CRC-aided list decoding, wherein incorrect decoding paths are rejected detected only after reaching the last information bit, the Viterbi decoder detects incorrect decisions "on the fly'' after a short delay. Whenever an incorrect decision is detected, the successive cancellation decoder is set back to the corresponding bit-channel, and then restarts its computation using the correct bit value provided by the Viterbi decoder.

Defined through a certain 2 × 2 matrix called Arikan's kernel, polar codes are known to achieve the symmetric capacity of binary-input discrete memoryless channels under the successive cancellation (SC) decoder. Yet, for short block-lengths, polar codes fail to deliver a compelling performance under the low complexity SC decoding scheme. Recent studies provide evidence for improved performance when Arikan's kernel is replaced with larger kernels that have smaller scaling exponents. However, for ℓ×ℓ kernels the time complexity of the SC decoding increases by a factor of 2ℓ. In this paper we study a special type of kernels called permuted kernels. The advantage of these kernels is that the SC decoder for the corresponding polar codes can be viewed as a permuted version of the SC decoder for the conventional polar codes that are defined through Arikan's kernel. This permuted successive cancellation (PSC) decoder outputs its decisions on the input bits according to a permuted order of their indices. We introduce an efficient PSC decoding algorithm and show simulations for two 16 × 16 permuted kernels that have better scaling exponents than Arikan's kernel.

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n, k, d]-(α) MSR code C over Fqstores a file F consisting of αk symbols over Fqamong n nodes, each storing α symbols, in such a way that: 1) the file F can be recovered by downloading the content of any k of then nodes and 2) the content of any failed node can be reconstructed by accessing any d of the remaining n - 1 nodes and downloading α/(d-k+1) symbols from each of these nodes. In practice, the file F is typically available in uncoded form on some k of the n nodes, known as systematic nodes, and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only. Such codes are called systematic-repair MSR codes. Unfortunately, finite-α constructions of [n, k, d] MSR codes are known only for certain special cases: either low rate, namely k/n ≤ 0.5, or high repair connectivity, namely d = n - 1. Our main result in this paper is a finite-α construction of systematic-repair [n, k, d] MSR codes for all possible values of parameters n, k, d. We also introduce a generalized construction for [n, k] MSR codes to achieve the optimal repair bandwidth for all values of d simultaneously.

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n, k, d]-(α) MSR code C over Fqis defined as follows. Using such a code C, a file F consisting of αk symbols over Fq can be distributed among n nodes, each storing α symbols, in such a way that: . the file F can be recovered by downloading the content of any k of the n nodes; and . the content of any failed node can be reconstructed by accessing any d of the remaining n -1 nodes and downloading α/(d-k+1) symbols from each of these nodes. A common practical requirement for regenerating codes is to have the original file F available in uncoded form on some k of the n nodes, known as systematic nodes. In this case, several authors relax the defining node-repair condition above, requiring the optimal repair bandwidth of dα/(d-k+1) symbols for systematic nodes only. We shall call such codes systematic-repair MSR codes. Unfortunately, explicit constructions of [n, k, d] MSR codes are known only for certain special cases: either low rate, namely k/n ≤ 0.5, or high repair connectivity, namely d = n -1. Although setting d = n - 1 minimizes the repair bandwidth, it may be impractical to connect to all the remaining nodes in order to repair a single failed node. Our main result in this paper is an explicit construction of systematic-repair [n, k, d] MSR codes for all possible values of parameters n, k, d. In particular, we construct systematic-repair MSR codes of high rate k/n > 0.5 and low repair connectivity k ≤ d ≤ n - 1. Such codes were not previously known to exist. In order to construct these codes, we solve simultaneously several repair scenarios, each of which is expressible as an interference alignment problem. Extension of our results beyond systematic repair remains an open problem.

Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic k-server PIR, the database is replicated among k non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers. However, another important cost parameter is the storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2 (or k, in the case of k-server PIR). In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that all known k-server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the n bits of the database among s + r servers, each storing n/s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific k-server PIR protocol being emulated. For every fixed k, the resulting storage overhead (s +r)/s approaches 1 as s grows; explicitly we have equation. Moreover, in the special case k = 2, the storage overhead is only 1 + 1/s. In order to achieve these results, we introduce and study a new kind of binary linear codes, called here k-server PIR codes. Finally, we show how such codes can be constructed from multidimensional cubic, from Steiner systems, and from one-step majority-logic decodable codes.

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversal. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound (or slightly weaker ones) is the assignment of weights to the hypergraph's vertices in a way that they satisfy the constraints in the linear programming problem. In order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases significantly reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the Z channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the nonbinary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion channel, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for single-deletion-correcting codes. Since the deletion and grain-error channels have a similar structure for a single error, we also improve upon the existing upper bounds on single-grain error-correcting codes. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other channels, and in particular for those where the error spheres sizes are not all the same. This paper studies this method in its most general setup. We first show that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound or slightly weaker ones is the assignment of weights to the hypergraph's vertices in a way that the satisfy the constraints in the linear programming problem. Every valid assignment yields an upper bound and the goal is to find assignments that provide strong upper bounds. We show that for graphs which satisfy a monotonicity property it is possible to find a general formula for such an assignment. Lastly, in order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases can significantly reduce the number of variables and constraints in the linear programming problem. All of our results will be demonstrated and calculated for the Z channel which will be a case study in our work.

In this paper we study a generalization of the sphere packing bound for channels that are not regular (the size of balls with a fixed radius is not necessarily the same). Our motivation to tackle this problem is originated by a recent work by Kulkarni and Kiyavash who introduced a method, based upon tools from hypergraph theory, to calculate explicit upper bounds on the cardinalities of deletion-correcting codes. Under their setup, the deletion channel is represented by a hypergraph such that every deletion ball is a hyperedge. Since every code is a matching in the hypergraph, an upper bound on the codes is given by an upper bound on the largest matching in a hypergraph. This bound, called here the generalized sphere packing bound, can be found by the solution of a linear programming problem. We similarly study and analyze specific examples of error channels. We start with the Z channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the non-binary limited magnitude channel both for symmetric and asymmetric errors. We focus on the case of single error and derive upper bounds on the generalized sphere packing bound in this channel. We follow up on the deletion case, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for the single deletion case. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.