Search

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. These codes can correct a small number of erasures by accessing only a small number of remaining coordinates. An $(n,r,h,a,q)$-LRC is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $g=n/r$ local groups each of size $r$. It has $h$ global parity checks and each local group has $a$ local parity checks. Such an LRC is Maximally Recoverable (MR), if it corrects all erasure patterns which are information-theoretically correctable under the stipulated structure of local and global parity checks. We show the first non-trivial lower bounds on the field size required for MR LRCs. When $a,h$ are constant and the number of local groups $g \ge h$, while $r$ may grow with $n$, our lower bound simplifies to $q\ge \Omega_{a,h}\left(n\cdot r^{\min\{a,h-2\}}\right).$ No superlinear (in $n$) lower bounds were known prior to this work for any setting of parameters. MR LRCs deployed in practice have a small number of global parities, typically $h=2,3$. We complement our lower bounds by giving constructions with small field size for $h\le 3$. For $h=2$, we give a linear field size construction. We also show a surprising application of elliptic curves and arithmetic progression free sets in the construction of MR LRCs., Comment: Conference version to appear in Symposium on Discrete Algorithms (SODA) 2018

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O ( k∈ ) were known only for codes of rate ∈ Ω(1/ ∈ ), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every ∈ > 0 and α > 0, for infinitely many k , there exists a code C which encodes messages of length k with rate 1 − α , and is locally decodable from a constant fraction of errors using O ( k∈ ) queries and time. These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.

Consider a linear [n,k,d]_q code C. We say that that i-th coordinate of C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst-case distance and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality for parity checks and the ability to correct erasures beyond the minimum distance.

We show that for any set A in a finite Abelian group G that has at least c|A|^3 solutions to a"1+a"2=a"3+a"4, a"[email protected]?A there exist sets A^'@?A and @[email protected]?G, @L={@l"1,...,@l"t}, [email protected]?c^-^1log|A| such that A^' is contained in {@?"j"="1^[email protected]"[email protected]"j|@e"[email protected]?{0,-1,1}} and A^' has @?c|A|^3 solutions to a"1^'+a"2^'=a"3^'+a"4^', a"i^'@?A^'. We also study so-called symmetric sets or, in other words, sets of large values of convolution.

A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user and the servers. A large amount of effort has been invested by researchers over the last decade in search for efficient PIR schemes. A number of different schemes [6, 4, 19] have been proposed, however all of them ended up with the same communication complexity of O(n1/3). The best known lower bound to date is 5logn by [17]. The tremendous gap between upper and lower bounds is the focus of our paper. We show an Ω(n1/3) lower bound in a restricted model that nevertheless captures all known upper bound techniques. Our lower bound applies to bilinear group based PIR schemes. Abilinear PIR scheme is a one round PIR scheme, where user computes the dot product of servers’ responses to obtain the desired value of the i-th bit. Every linear scheme can be turned into a bilinear one with an asymptotically negligible communication overhead. A group based PIR scheme is a PIR scheme that involves servers representing database by a function on a certain finite group G, and allows user to retrieve the value of this function at any group element using the natural secret sharing scheme based on G. Our proof relies on representation theory of finite groups.

Let [t] represent a finite population with t elements. Suppose we have an unknown d-family of k-subsets Γ of [t]. We refer to Γ as the set of positive k-complexes. In the group testing for complexes problem, Γ must be identified by performing 0, 1 tests on subsets or pools of [t]. A pool is said to be positive if it completely contains a complex; otherwise the pool is said to be negative. In classical group testing, each member of Γ is a singleton. In this paper, we exhibit and analyze a probabilistic trivial two-stage algorithm that identifies the positive complexes.

A square matrix V is called rigid if every matrix $${V^\prime}$$V? obtained by altering a small number of entries of V has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper, we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field $${\mathbb{F}_2.}$$F2. Stated informally, we conjecture that under a suitable embedding of $${\mathbb{F}_2^n}$$F2n into $${\mathbb{R}^n,}$$Rn, vectors arising from a low-dimensional $${\mathbb{F}_2}$$F2-linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low-dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.

Consider a possibly non-linear (n,K,d)_q code. Coordinate i has locality r if its value is determined by some r other coordinates. A recent line of work obtained an optimal trade-off between information locality of codes and their redundancy. Further, for linear codes meeting this trade-off, structure theorems were derived. In this work we give a new proof of the locality / redundancy trade-off and generalize structure theorems to non-linear codes.

Let f in F_q[x] be a polynomial of degree d _ q=2: It is well-known that f can be uniquely recovered from its values at some 2d points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that a k-sparse polynomial f 2 Fq[x] of degree d _ q=2 can be recovered from its values at O(k) randomly chosen points, even if a small fraction of the values of f are adversarially corrupted. Our proof relies on an iterative technique for analyzing the rank of a random minor of a matrix.We use the same technique to establish a collection of other results. Specifically,_ We show that restricting any linear [n; k; _n]q code to a randomly chosen set of O(k) coordinates with highprobability yields an asymptotically good code. _ We improve the state of the art in locally decodable codes,showing that similarly to Reed Muller codes matching vector codes require only a constant increase in querycomplexity in order to tolerate a constant fraction of errors. This result yields a moderate reduction in thequery complexity of the currently best known codes. _ We improve the state of the art in constructions of explicit rigid matrices. For any prime power q and integers n and d we construct an explicit matrix M with exp(d) _ n rows and n columns such that the rank of M stays above n=2 even if every row of M is arbitrarily altered in up to d coordinates. Earlier, such constructions were available only for q = O(1) or q = (n)

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point $v \in \mathbb{F}_2^n$ and a linear space $L\subseteq \mathbb{F}_2^n$ of dimension k NCP asks to find a point l *** L that minimizes the (Hamming) distance from v . It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best efficient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of O (k /c ) for an arbitrary constant c , and a randomized algorithm that achieves an approximation ratio of O (k /logn ). In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work. Specifically, we obtain: A polynomial time O (n /logn )-approximation algorithm; An n O (s ) time O (k log(s ) n / logn )-approximation algorithm, where log(s ) n stands for s iterations of log, e.g., log(2) n = loglogn ; An $n^{O(\log^* n)}$ time O (k /logn )-approximation algorithm. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space $L\subseteq \mathbb{F}_2^n$ of dimension k RPP asks to find a point $v\in \mathbb{F}_2^n$ that is far from L . We say that an algorithm achieves a remoteness of r for the RPP if it always outputs a point v that is at least r -far from L . In this paper we present a deterministic polynomial time algorithm that achieves a remoteness of ***(n logk / k ) for all k ≤ n /2. We motivate the remote point problem by relating it to both the nearest codeword problem and the matrix rigidity approach to circuit lower bounds in computational complexity theory.

We study the complexity of deciding whether a given homogeneous multivariate polynomial has a non- trivial root over a finite field. Given a homogeneous algebraic circuit C that computes an n- variate polynomial p(x) of degree d over a finite field Fq, we wish to determine if there exists a nonzero xisinFq n with C(x)=0. For constant n there are known algorithms for doing this efficiently. However for linear n, the problem becomes NP hard. In this paper, using interesting algebraic techniques, we show that if d is prime and n>d/2, the problem can be solved over sufficiently large finite fields in randomized polynomial time. We complement this result by showing that relaxing any of these constraints makes the problem intractable again.

A q -query Locally Decodable Code (LDC) encodes an n -bit message x as an N -bit codeword C ( x ), such that one can probabilistically recover any bit x i of the message by querying only q bits of the codeword C ( x ), even after some constant fraction of codeword bits has been corrupted. We give new constructions of three query LDCs of vastly shorter length than that of previous constructions. Specifically, given any Mersenne prime p = 2 t − 1, we design three query LDCs of length N = exp( O ( n 1/ t )), for every n . Based on the largest known Mersenne prime, this translates to a length of less than exp( O ( n 10 − 7 )) compared to exp( O ( n 1/2 )) in the previous constructions. It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of length N = exp( n O (1/log log n ) ) for infinitely many n . We also obtain analogous improvements for Private Information Retrieval (PIR) schemes. We give 3-server PIR schemes with communication complexity of O ( n 10 − 7 ) to access an n -bit database, compared to the previous best scheme with complexity O ( n 1/5.25 ). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity n O (1/log log n ) ) for infinitely many n . Previous families of LDCs and PIR schemes were based on the properties of low-degree multivariate polynomials over finite fields. Our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set.

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major goal of LDC related research is to establish the optimal trade-off between length and query complexity of such codes. Recently [Y] introduced a novel technique for constructing locally decodable codes and vastly improved the upper bounds for code length. The technique is based on Mersenne primes. In this paper we extend the work of [Y] and argue that further progress via these methods is tied to progress on an old number theory question regarding the size of the largest prime factors of Mersenne numbers. Specifically, we show that every Mersenne number m=2^t-1 that has a prime factor p>m^\gamma yields a family of k(\gamma)-query locally decodable codes of length Exp(n^{1/t}). Conversely, if for some fixed k and all \epsilon > 0 one can use the technique of [Y] to obtain a family of k-query LDCs of length Exp(n^\epsilon); then infinitely many Mersenne numbers have prime factors arger than known currently., Comment: 18 pages

This paper deals with (s,l)-cover-free families or superimposed (s,l)-codes. They generalize the concept of superimposed s-codes and have several applications for cryptography and group testing. We present a new asymptotic bound on the rate of optimal codes and develop some constructions.