10 July 2018 in IEEE Transactions on Information Theory
Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size q. Recently, it was proved through the extension of construction by Tamo and Barg that the length of q-ary optimal locally repairable codes can be q +1 by Jin et al. Surprisingly, Barg et al. presented a few examples of q-ary optimal locally repairable codes of small distance and locality with code length achieving roughly q 2 . Very recently, it was further shown in the work of Li et al. that there exist q-ary optimal locally repairable codes with the length bigger than q+1 and the distance proportional to n. Thus, it becomes an interesting and challenging problem to construct new families of q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen.
10 January 2019 in IEEE Transactions on Information Theory
A locally repairable code (LRC) with locality r allows for the recovery of any erased codeword symbol using only r other codeword symbols. A Singleton-type bound dictates the best possible tradeoff between the dimension and distance of LRCs-an LRC attaining this tradeoff is deemed optimal. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary or, for that matter, even if the alphabet needs to grow at all with the block length. Indeed, for small code distances 3 and 4, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances d ≥ 5, the code length n of an optimal LRC over an alphabet of size q must be at most roughly O(dq 3 ). For the case d = 5, our upper bound is O(q 2 ). We complement these bounds by showing the existence of optimal LRCs of length Ω d,r (q 1+1/〈(d-3)/2〉 ) when d r + 2. These bounds match when d = 5, thus pinning down n = Θ(q 2 ) as the asymptotically largest length of an optimal LRC for this case.
8 March 2022 in IEEE Transactions on Information Theory
A block code is called a locally recoverable code (LRC for short) with $(r,\delta)$ -locality, if subject to any $\delta -1$ erasure failures, every symbol in the encoding can still be recovered by accessing at most $r$ other symbols. Recently, it was discovered by several authors that a $q$ -ary optimal $(r,\delta)$ -LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than $q+1$ . This is quite different from the classical $q$ -ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special cases). In this paper, we further investigate constructions of optimal $(r,\delta)$ -LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of $\mathbb {F}_{q}$ . We manage to show the existence of these disjoint subsets. Thus, this yields an optimal $(r,\delta)$ -LRC with code length $\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ , where $d$ is the minimum distance. In particular, to our surprise, for $\delta =2$ this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami et al. (2018) for $d\geq 7$ . In addition, for $d=6$ , we are able to remove the constraint required in Jin (2019) that $q$ is even.
14 March 2019 in IEEE Transactions on Information Theory
3 May 2017 in IEEE Transactions on Information Theory
A pure quantum state is called k-uniform if all its reductions to k-qudit are maximally mixed. We investigate the general constructions of k-uniform pure quantum states of n subsystems with d levels. We provide one construction via symmetric matrices and the second one through the classical error-correcting codes. There are three main results arising from our constructions. First, we show that for any given even n ≥ 2, there always exists an n/2-uniform n-qudit quantum state of level p for sufficiently large prime p. Second, both constructions show that there exist k-uniform n-qudit pure quantum states such that k is proportional to n, i.e., k = Ω(n) although the construction from symmetric matrices in general outperforms the one by error-correcting codes. Third, our symmetric matrix construction provides a positive answer to the open question on whether there exists a 3-uniform n-qudit pure quantum state for all n ≥ 8. In fact, we can further prove that, for every k, there exists a constant Mk such that there exists a k-uniform n-qudit quantum state for all n ≥ Mk. In addition, by using the concatenation of algebraic geometry codes, we give an explicit construction of k-uniform quantum state when k tends to infinity.