Search

A $k$-query locally decodable code (LDC) $C$ allows one to encode any $n$-symbol message $x$ as a codeword $C(x)$ of $N$ symbols such that each symbol of $x$ can be recovered by looking at $k$ symbols of $C(x)$, even if a constant fraction of $C(x)$ have been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ may result in an MVC with $k\leq 2^r$ and $N=\exp(\exp(O((\log n)^{1-1/r} (\log\log n)^{1/r})))$. The $m$ is {\em good} if it is possible to have $k, Comment: The Computer Journal

We construct locally decodable codes (LDCs) to correct insertion-deletion errors in the setting where the sender and receiver share a secret key or where the channel is resource-bounded. Our constructions rely on a so-called "Hamming-to-InsDel" compiler (Ostrovsky and Paskin-Cherniavsky, ITS '15 & Block et al., FSTTCS '20), which compiles any locally decodable Hamming code into a locally decodable code resilient to insertion-deletion (InsDel) errors. While the compilers were designed for the classical coding setting, we show that the compilers still work in a secret key or resource-bounded setting. Applying our results to the private key Hamming LDC of Ostrovsky, Pandey, and Sahai (ICALP '07), we obtain a private key InsDel LDC with constant rate and polylogarithmic locality. Applying our results to the construction of Blocki, Kulkarni, and Zhou (ITC '20), we obtain similar results for resource-bounded channels; i.e., a channel where computation is constrained by resources such as space or time.

Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit local algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity. In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n , constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp(Õ(√log n )) (for LCCs) and (log n ) O (log log n ) (for LTCs). In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any o ( n ) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code C ⊂ Σ K n is an r -query affine invariant locally correctable code (LCC), where K is a finite field and Σ is a finite alphabet, then the number of codewords in C is at most exp( O K,r,|Σ| ( n r −1)) . Also, we show that if C ⊂ Σ K n is an r -query affine invariant locally testable code (LTC), then the number of codewords in C is at most exp( O K,r,|Σ| ( n r −2)) . The dependence on n in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty, and Sudan (ITCS’13) constructed affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM’11) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems, which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, up to a small error in the Gowers norm.

A locally decodable code (LDC) C from {0,1} to the k to {0,1} to the n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of O(1)-query LDCs have super-polynomial block length.\ud The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O(1)-query relaxed LDCs achieve blocklength n is order of k to the power of 1 plus gamma for an arbitrarily small constant.\ud We prove a lower bound which shows that O(1)-query relaxed LDCs cannot achieve blocklength n = k to the power of 1 + o(1). This resolves an open problem raised by Goldreich in 2004.

We survey the state of the art in constructions of locally testable codes, locally decodable codes and locally correctable codes of high rate.

In this study, the authors consider the designing of a new set of uniquely decodable codes for uncoded synchronous overloaded code division multiple access for the number of codes exceeding the assigned code length. For the construction, the proposed recursive method at iteration-k generates a matrix that can be classified into k orthogonal subsets of different dimensions. Out of them, all besides the largest (binary Hadamard) one are ternary in nature. There resides an inbuilt twin tree structured cross-correlation hierarchy that facilitates an advantageous balance between the auto and intergroup cross-correlation for the signatures in a subset. This opportunity is further leveraged by the proposed multi-stage detector to maintain the uniquely decodable (errorless) nature of the matrices for noiseless transmission. The simple logic of matched filtering serving as the basic designing block of the decoder provides an enormous saving over the complexity of optimum maximum likelihood decoder. For the noisy channel, the authors derive the theoretical expression of the average bit error rate for the individual subset. Moreover, the authors explain the role of the two factors (cardinality of the subset, and net level of interference) in being responsible for the non-uniformity in the order of their error performance.

A locally decodable code (LDC) maps $K$ source symbols, each of size $L_{w}$ bits, to $M$ coded symbols, each of size $L_{x}$ bits, such that each source symbol can be decoded from $N \leq M$ coded symbols. A perfectly smooth LDC further requires that each coded symbol is uniformly accessed when we decode any one of the messages. The ratio $L_{w}/L_{x}$ is called the symbol rate of an LDC. The highest possible symbol rate for a class of LDCs is called the capacity of that class. It is shown that given $K, N$ , the maximum value of capacity of perfectly smooth LDCs, maximized over all code lengths $M$ , is $C^{*}=N\left ({1+1/N+1/N^{2}+\cdots +1/N^{K-1}}\right)^{-1}$ . Furthermore, given $K, N$ , the minimum code length $M$ for which the capacity of a perfectly smooth LDC is $C^{*}$ is shown to be $M = N^{K}$ . Both of these results generalize to a broader class of LDCs, called universal LDCs. The results are then translated into the context of PIRmax, i.e., Private Information Retrieval subject to maximum (rather than average) download cost metric. It is shown that the minimum upload cost of capacity achieving PIRmax schemes is $(K-1)\log N$ . The results also generalize to a variation of the PIR problem, known as Repudiative Information Retrieval (RIR).

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet, we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist. In this paper, we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester (“well-structured tester”). We show that a family of codes is smoothly locally testable if and only if it has a well-structured tester. As a case study we show that the standard tester for the Hadamard code is “well-structured,” giving an alternative proof of the local testability of the Hadamard code, originally proved by (Blum, Luby, Rubinfeld, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben-Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.

In this paper, we propose three constructions of locally repairable codes based on fractional repetition (FR) codes. We also derive the bounds on the maximum file size stored with locally repairable FR codes with locality 2 and 3, respectively. Construction 1 results in a locally repairable FR code with locality 2. It has repetition degree ρ = 2, and attains the bound on the maximum file size we derived. The availability of this code is designed to be ρ − 1 = 1. Construction 2 results in a code which has larger availability ρ − 1 = 2 so that multiple node failures can be ‘locally’ repaired. This code also attains the bound on the maximum file size but with larger number of storage nodes. Construction 3 is a result of reducing the number of storage nodes.

In this work, we give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first capacity-achieving locally list-decodable codes (over constant-sized alphabet); the first capacity achieving} globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known.Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes. We show that tensor powers of (globally) list-recoverable codes are approximately locally list-recoverable, and that the approximately modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions of high-rate globally list-recoverable codes and high-rate locally decodable codes finishes the construction.

Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. Despite decades of study, the optimal trade-off between query complexity and codeword length is far from understood. In this work, we give a new characterization of LDCs using distributions over Boolean functions whose expectation is hard to approximate (in~$L_\infty$~norm) with a small number of samples. We coin the term `outlaw distributions' for such distributions since they `defy' the Law of Large Numbers. We show that the existence of outlaw distributions over sufficiently `smooth' functions implies the existence of constant query LDCs and vice versa. We give several candidates for outlaw distributions over smooth functions coming from finite field incidence geometry, additive combinatorics and from hypergraph (non)expanders. We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters., Comment: A preliminary version of this paper appeared in the proceedings of ITCS 2017

Instantly Decodable Network Codes are of great interest in broadcast applications because of their properties like low decoding delay, low encoding and decoding complexities, and simple receiver requirements. This work explores two different multicast broadcast scenarios and gives instantly decodable index codes that perform better than codes in existing literature. First, we describe our novel Unequal Error Protection scheme that achieves theoretical optimality and illustrate it through examples. In order sensitive or delay sensitive applications, based on an earlier decodability at the receivers' end, a packet can be classified as high priority (HP) packets or low priority (LP) packets. We introduce a practical algorithm that improves the packet retransmission technique of Muhammed et al. (Proceedings of the 2013 IEEE International Conference on Communications (ICC), Budapest, pp. 5120-5125) for reliable multicast in the instantly decodable network coding framework. Our scheme improves the delay and total completion time by optimizing the number of instantly decodable network code packet transmissions from the source. Further, simulation results with a comparative study show considerable improvement in Quality of Experience (QoE) for the end-users.

In a recent result, Dachman-Soled et al. (TCC 2015) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was \(\varOmega (\log n)\), meaning that if the original message size was n blocks, then \(\varOmega (\log n)\) blocks of the codeword had to be accessed upon each decode and update instruction.

International audience; Proofs of retrievability (PoR) are probabilistic protocols which ensure that a client can recover a file he previously stored on a server. Good PoRs aim at reaching an efficient trade-off between communication complexity and storage overhead, and should be usable an unlimited number of times. We present a new unbounded-use PoR construction based on a class of locally decodable codes, namely the lifted codes of Guo et. al.. Our protocols feature sublinear communication complexity and very low storage overhead. Moreover, the various parameters can be tuned so as to minimize the communication complexity (resp. the storage overhead) according to the setting of concern.

Locally correctable codes are error-correcting codes that allow a single bit of the codeword to be recovered by looking up a small subset of the coordinates of the received word. In this work, we generalize the concept of traditional locally correcting to locally correcting multiple bits, and present a family of codes which allow multiple bits to be recovered with probability approaching 1 by visiting a small number of locations of the received word, even when a constant fraction of errors exist. Moreover, our codes are of high rate.

A local tester for a code probabilistically views a small set of coordinates of a given word and based on this local view accepts code words with probability one while rejecting words far from the code with constant probability. A local tester for a code is said to be "robust" if the local views of the tester are far from acceptable views when the word being tested is far from the code. Robust testability of codes play a fundamental role in constructions of probabilistically checkable proofs where robustness is a critical element in composition. In this work we consider a broad class of codes, called lifted codes, that include codes formed by low-degree polynomials, and show that an almost natural test, extending a low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our result is clean and general -- the robustness of the test depends only on the distance of the code being lifted, and is positive whenever the distance is positive. We use our result to get the first robust low-degree test that works when the degree of the polynomial being tested is more than half the field size. Our results also show that the high-rate codes of Guo et al. (ITCS 2013) are robustly locally testable with sub linear query complexity. Guo et al. Also show several other interesting classes of locally testable codes that can be derived from lifting and our result shows all such codes have robust testers, at the cost of a quadratic blow up in the query complexity of the tester. Of technical interest is an intriguing relationship between tensor product codes and lifted codes that we explore and exploit.

Locally correctable codes are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. Recently Kopparty et. al. [1] and Guo et. al. [2] presented multiplicity codes and lifted Reed-Solomon codes, respectively, which are two families of high-rate locally correctable codes. In this paper, we generalize the method of multiplicities and provide a new construction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the codes in [1] and [2].

In this work, we revisit the structure of weight matrices for Linear Dispersion STBCs to admit ML decoding with low-complexity. We first propose novel sufficient design criteria for linear STBCs considering an arbitrary number of antennas and an arbitrary coding rate. Then we apply the derived criteria to three families of codes, multi-group decodable, fast decodable, and fast-group decodable codes. We provide analytical proofs showing that the ML-decoding complexity of such codes depends only on the weight matrices and their ordering and not on the channel gains or the number of antennas and explaining why the so far used Hurwitz-Radon theory-based approaches do not exactly determine the complexity of all classes of STBCs under ML decoding.

In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound.