We study the problem of constructing (ρ,L)-list-decodable codesC⊆ Fnqwith smallqusing minimal randomness. The central goal is to generate codes of rate approaching the Elias bound, that is, rate at least 1 −h(ρ) −O(1/L), using significantly fewer random bits than required by uniformly random linear codes. Prior combinatorial constructions achieve this usingO(Ln) random bits via graph-based methods. In this work, we present two new and fully algebraic constructions that match this randomness efficiency while offering greater simplicity and structural transparency. Our first construction, a generalization of theWozencraft ensemble, achieves the Elias bound with onlyLnrandom bits; its dual achieves the Gilbert–Varshamov bound, and both codes support quasilinear-time encoding. Our second construction uses 2nLrandom bits and yields a code whose dual also achieves the Elias bound. These dual properties are critical for applications in areas such as cryptography. Our analysis proceeds by designing codes that replicate key local properties of random linear codes, allowing us to invoke known results to deduce list-decodability. As a final contribution, we prove a lower bound showing that any construction relying solely on such local approximation must use at leastL(1 −R)nlog2(q) random bits to obtain rate-Rcodes over an alphabet of sizeq.

In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code $\mathcal{C} \subseteq [q]^n$ is $(p,\ell,L)$-list-recoverable if for all tuples of input lists $(Y_1,\dots,Y_n)$ with each $Y_i \subseteq [q]$ and $|Y_i|=\ell$ the number of codewords $c \in \mathcal{C}$ such that $c_i \notin Y_i$ for at most $pn$ choices of $i \in [n]$ is less than $L$; list-decoding is the special case of $\ell=1$. In recent work by Resch, Yuan and Zhang~(ICALP~2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes $p_*:=p_*(q,\ell,L)$ with the property that for all $ε>0$ (a) there exist infinite families positive-rate $(p_*-ε,\ell,L)$-list-recoverable codes, and (b) any $(p_*+ε,\ell,L)$-list-recoverable code has rate $0$. In fact, in the latter case the code has constant size, independent on $n$. However, the constant size in their work is quite large in $1/ε$, at least $|\mathcal{C}|\geq (\frac{1}ε)^{O(q^L)}$. Our contribution in this work is to show that for all choices of $q,\ell$ and $L$ with $q \geq 3$, any $(p_*+ε,\ell,L)$-list-recoverable code must have size $O_{q,\ell,L}(1/ε)$, and furthermore this upper bound is complemented by a matching lower bound $Ω_{q,\ell,L}(1/ε)$. This greatly generalizes work by Alon, Bukh and Polyanskiy~(IEEE Trans.\ Inf.\ Theory~2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for $q=2$ and even $L$, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work.

In this work, we consider the task of generating listdecodable codes over small (say, binary) alphabets using as little randomness as possible. Specifically, we hope to generate codes achieving what we term the Elias bound, which means that they are ($\rho, L$) -list-decodable with rate$R \geq 1-h(\rho)-O(1 / L)$. A long line of work shows that uniformly random linear codes (RLCs) achieve the Elias bound: hence, we know$O\left(n^{2}\right)$random bits suffice. Prior works (Guruswami and Mosheiff, FOCS 2022; Putterman and Pyne, ITCS 2024) demonstrate that just$O(L n)$random bits suffice, via puncturing of low-bias codes. These recent constructions are essentially combinatorial, and rely (directly or indirectly) on graph expansion. We provide two new constructions, which are algebraic. Compared to prior works, our constructions are considerably simpler and more direct. Furthermore, our codes are designed in such a way that their duals are also quite easy to analyze. Our first construction which can be seen as a generalization of the celebrated Wozencraft ensemble - achieves the Elias bound and consumes$L n$random bits. Additionally, its dual code achieves the Gilbert-Varshamov bound with high probability, and both the primal and dual admit quasilinear-time encoding algorithms. The second construction consumes$2 L n$random bits and yields a code where both it and its dual achieve the Elias bound. In all of the above cases - including the prior works achieving randomness complexity$O(L n)$- the codes are designed to “approximate” RLCs. More precisely, for a given locality parameter$L$we construct codes achieving the same$L$-local properties as RLCs. This allows one to appeal to known list-decodability results for RLCs and thereby conclude that the code approximating an RLC also achieves the Elias bound (with high probability). As a final contribution, we indicate that such a proof strategy is inherently unable to generate list-decodable codes of rate$R$over$\mathbb{F}_{q}$with less than$L(1-R) n \log _{2}(q)$bits of randomness.

Reverse multiplication-friendly embeddings have played a crucial role in secure multiparty computation and zero-knowledge proofs. In this work, we generalize the notion of RMFEs todegree-DRMFEs. We present a general construction of degree-DRMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree-2 RMFEs. Furthermore, our theory is given in a unified manner for general Galois rings, which include both rings of the form Zpkand fields like Fpk, which have been treated separately in prior works. We present multiple concrete sets of parameters for degree-DRMFEs (includingD= 2), which can be useful for future works. In the recent work of (Cheon & Lee, Eurocrypt’22), the concept of adegree-D packing methodwas formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring. We show that the generalized notion of RMFEs todegree-D RMFEswhich, in spite of being “more algebraic” than packing methods, turn out to be essentially equivalent. Thus, our constructions of degree-DRMFEs are also degree-Dpacking methods.

Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful positive results about the list decoding of Reed-Solomon codes, results concerning the list decodability of Gabidulin codes in the rank metric are all negative so far. For example, in contrast to Reed-Solomon codes, which are always list decodable up to the Johnson bound in the Hamming metric, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of Gabidulin codes that are not even combinatorially list decodable beyond the unique decoding radius in the rank metric. Proving the existence of Gabidulin codes with good combinatorial list decodability in the rank metric has remained a long-standing open problem. In this paper, we resolve the aforementioned open problem by showing that, with high probability, random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding in the rank metric. In particular, they achieve list decoding capacity in the rank metric. Our work is significantly influenced by the recent break-throughs in the combinatorial list decodability of Reed-Solomon codes, especially the work by Brakensiek, Gopi, and Makam (STOC 2023). Our major conceptual and technical contributions, which may hold independent interest, consist of the following: (1) We initiate the study of “higher order MRD codes” and provide a novel unified theory, which runs parallel to the theory of “higher order MDS codes” developed by Brakensiek, Gopi, and Makam. (2) We prove a natural analog of the GM-MDS theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT, 2019), which we call the GM-MRD theorem. In particular, our GMMRD theorem for Gabidulin codes is strictly stronger than the GM-MDS theorem for Gabidulin codes proven by Yildiz and Hassibi.

A locally repairable code is called Singleton-optimal if it achieves the Singleton-type bound. Such codes are of great theoretic interest in the study of locally repairable codes. One of the major problems in this topic is to determine the maximum length of aq-ary Singleton-optimal locally repairable code with fixed locality and minimum distance. Unlike classical MDS codes, the maximum length of Singleton-optimal locally repairable codes is very sensitive to the minimum distance and locality. Thus, determining the maximum length of the Singleton-optimal locally repairable codes is more challenging and complicated. In literature, many efforts are paid to solve this problem especially for small distance and locality regime. Moreover, most of works also requires that (r+ 1)|nand the recovery sets are disjoint so as to simplify the argument,whereris locality andnis the code length. In this paper, we derive some upper bounds on the maximum length of Singleton-optimal locally repairable codes with minimum distance 5, 6 and 7 without the constraint that (r+ 1)|nand the recovery sets are disjoint.It turns out that even without this constraint we still obtain better upper bounds for codes with small locality and distance compared to known results. Furthermore, based on our upper bounds for codes with small distance and locality, we propose the propagation rule to derive some upper bounds for codes with relatively large distance and locality assuming that (r+1)|nand recovery sets are disjoint.

In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of$q\geq 2$. A code is called$(p,L)_{q}$-list-decodable if every radius pn Hamming ball contains less than L codewords;$(p,\ell ,L)_{q}$-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length$\ell $and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate$(p,\ell ,L)_{q}$-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by$p_{*}$, we in fact show that codes correcting a$p_{*}+\varepsilon $fraction of errors must have size$O_{\varepsilon }(1)$, i.e., independent of n. Such a result is typically referred to as a “Plotkin bound.” To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a$p_{*}-\varepsilon $fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.

In this paper, we construct many infinite families of distance-optimal codes with new parameters, some of which are BCH codes and quasi-cyclic codes. In particular, we report the first infinite family of binary distance-optimal BCH codes with the minimum distance 8. Secondly, several infinite families of binary BCH codes and quasi-cyclic codes are presented. Many codes in these families have optimal or best known parameters. Thirdly, we construct infinite families of binary cyclic$\left [{{n, \geq \frac {n+1}{2},d}}\right]_{2}$codes with minimum distances$d \geq \lceil \frac {n-1}{\prod _{i=1}^{s}p_{i}}\rceil $,$n=(2^{p_{1}}-1)(2^{p_{2}}-1) \cdots (2^{p_{s}}-1)$,$p_{1}, \ldots, p_{s}$are different primes. Our construction extends the main result of a recent paper published by Sun et al. to much more general binary cyclic codes with various lengths. We also construct an infinite family of binary quasi-cyclic codes with the rate around$\frac {1}{2}$and relative minimum distance lower bounded by$O\left ({{\frac {1}{\log _{2} \log _{2} n}}}\right)$.

A secret sharing scheme enables the dealer to share a secret amongnparties. A classic secret sharing scheme takes the numbernof parties and the secret as the input. Ifnis not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev [8] first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work [8], [9], and [2], evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in [2] are inspired by the scheme given in [8], namely, these schemes rely on the scheme for st-connectivity which allows to generate infinite number of shares. In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Our first scheme is an evolvingk-threshold secret sharing scheme with share sizek1+ϵlogtfor any constant ϵ > 0. Thus, our scheme achieves almost the same share size as in [8]. Moreover, our scheme is obtained by a direct construction while the scheme in [8] that achieves the (k- 1) logtshare size is obtained by a recursive construction, which makes their structure complicated. Our second scheme is an evolvingkt-threshold secret sharing scheme with any sequence {kt}∞t=1of threshold values that has share sizet4. This scheme improves the share size by logtgiven in [9], where a dynamic evolvingkt-threshold secret sharing scheme with the share sizeO(t4logt) was proposed. In addition, we also show that if the threshold valuesktgrow in rate ⌊tβ⌋ for a real β ∈ (0, 1), then we have a dynamic evolving threshold secret sharing scheme with the share sizeO(t4β). Our last scheme is an evolving (αt, βt)-ramp secret sharing scheme with constant share size for some α, β. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique in [9] can also transform all of our schemes to a robust scheme as our scheme is linear.

In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a "Plotkin bound." To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.

A pure quantum state of$n$parties associated with the Hilbert space$\mathbb {C}^{d_{1}}\otimes \mathbb {C} ^{d_{2}}\otimes \cdots \otimes \mathbb {C} ^{d_{n}}$is called$k$-uniform if all the reductions to$k$-parties are maximally mixed. The$n$partite system is called homogenous if the local dimensions$d_{1}=d_{2}=\cdots =d_{n}$, while it is called heterogeneous if the local dimensions are not all equal.$k$-uniform sates play an important role in quantum information theory. There are much progress in characterizing and constructing$k$-uniform states in homogeneous systems. However, the study of entanglement for heterogeneous systems is much more challenging than that for the homogeneous case. There are very few results known for the$k$-uniform states in heterogeneous systems for$k>3$. We present two general methods to construct$k$-uniform states in the heterogeneous systems for general$k$. The first construction is derived from the error correcting codes by establishing a connection between irredundant mixed orthogonal arrays and error correcting codes. We can produce many new$k$-uniform states such that the local dimension of each subsystem can be a prime power. The second construction is derived from a matrix$H$meeting the condition that$H_{A\times \bar {A}}+H^{T}_{\bar {A}\times A}$has full rank for any row index set$A$of size$k$. These matrix construction can provide more flexible choices for the local dimensions, i.e., the local dimensions can be any integer (not necessarily prime power) subject to some constraints. Our constructions imply that for any positive integer$k$, one can construct$k$-uniform states of a heterogeneous system in many different Hilbert spaces.

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 Guruswamiet 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.

For an integer q ≥ 2, a perfect q-hash code C is a block code over [q] ≔ {1, …, q} of length n in which every subset {c1, c2, …, cq} of q elements is separated, i.e., there exists i ∊ [n] such that {proji(c1), …, proji(cq)} = [q], where proji(cj) denotes the ith position of cj. Finding the maximum size M(n, q) of perfect q-hash codes of length n, for given q and n, is a fundamental problem in combinatorics, information theory, and computer science. In this paper, we are interested in asymptotical behavior of this problem. More precisely speaking, we will focus on the quantity . A well-known probabilistic argument indicates [10, 12]. This is still the best-known lower bound so far except for the case q = 3 for which Körner and Matron [13] found that the concatenation technique could lead to perfect 3-hash codes that could beat this probabilistic lower bound. This improved lower bound on R3 was discovered in 1988 and there has been no progress of this lower bound on Rq for more than 30 years despite of some work on upper bounds on Rq. In this paper we show that this probabilistic lower bound can be improved for q = 4, 8 and all odd integers between 5 and 25,1 and all sufficiently large q with q (mod 4) ≠ 2. Although we are not able to prove that our construction can beat the probabilistic method for all q with q (mod 4) ≠ 2, the fact that our construction beat the probabilistic method for both small and large q sheds light on that our new construction might beat the previous lower bound for all q with q (mod 4) ≠ 2. Our idea is based on a modified concatenation differing from the concatenation [10] where both the inner and outer codes are separated. In our concatenation, the inner code is not necessarily a perfect q-hash code. This gives a more flexible choice of inner codes and hence we are able to improve the lower bound on Rq.

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is d = Θ(q), where q is the code alphabet size (in fact, d can be as big as q/4 in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing), we are able to locally recover arbitrarily large number k of coordinates of a Reed-Muller code simultaneously with error probability exp(-Ω(k)) at the cost of querying merely O(q2k) coordinates. It turns out that our local decoding of Reed-Muller codes shows (perhaps surprisingly) that accessing k locations is in fact cheaper than repeating the procedure for accessing a single location for k times. Precisely speaking, to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query Ω(qk2) coordinates. Thus, the query complexity of our local decoding is smaller for k = Ω(q). If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when k = Ω(qq). In addition, our local decoding is efficient, i.e., the decoding complexity is Poly(k, q). Construction of an interleaved codex is based on concatenation of a codex with a multiplication friendly pair, while the main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes).

Given a q-ary frequency hopping sequence set of length n and size M with Hamming correlation H, one can obtain a q-ary (nonlinear) cyclic code of length n and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets [1]. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool- martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region.

Locally recoverable codes are a class of block codes with an additional property called locality. A locally recoverable code with locality r can recover a symbol by reading at most r other symbols. Recently, it was discovered by several authors that a q-ary optimal locally recoverable code, i.e., a locally recoverable code achieving the Singleton-type bound, can have length much bigger than q+1. In this paper, we present both the upper bound and the lower bound on the length of optimal locally recoverable codes. Our lower bound improves the best known result in [Yuan Luo et al., 2018] for all distance d >= 7. This result is built on the observation of the parity-check matrix equipped with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure produces an optimal locally recoverable code if it satisfies a certain expansion property for subsets of F_q. To our surprise, this expansion property is then shown to be equivalent to a well-studied problem in extremal graph theory. Our upper bound is derived by an refined analysis of the arguments of Theorem 3.3 in [Venkatesan Guruswami et al., 2018].

At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD \(\mathbb {Z}_{2^k}\) that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo \(2^k\) , thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over \(\mathbb {Z}/p^{k}\mathbb {Z}\) (for any prime p and positive integer k ) that is perfectly secure against active adversaries corrupting a fraction of at most 1/3 players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most 1/2 players.

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(dq3). For the case d = 5, our upper bound is O(q2). We complement these bounds by showing the existence of optimal LRCs of length Ωd,r(q1+1/〈(d-3)/2〉) when d r + 2. These bounds match when d = 5, thus pinning down n = Θ(q2) as the asymptotically largest length of an optimal LRC for this case.

We investigate the list decodability of symbol-pair codes1in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type bound in the pair metric.1A symbol-pair code is referred to a code in the pair metric.

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 q2. 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.

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 trade-off between the dimension and distance of LRCs --- an LRC attaining this trade-off is deemed \emph{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,4$, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances $d \ge 5$, the code length $n$ of an optimal LRC over an alphabet of size $q$ must be at most roughly $O(d q^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/\lfloor(d-3)/2\rfloor})$ when $d \le 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.

Wachter-Zeh showed that every cover metric code can be list decoded up to the Johnson-like bound. Furthermore, it was shown that the efficient list decoding of cover metric codes up to the Johnson-like bound can be performed. From the work of Wachter-Zeh, one natural question is whether the Johnson-like bound can be improved. In this paper, we give a confirmative answer to this question by showing that the cover metric codes can be list decoded up to the Singleton bound. Our contributions consist of three parts. First, we prove that the list decodability of cover metric codes does not exceed the Singleton bound. Second, we show that, with high probability, a random cover metric code can be list decoded up to the Singleton bound, which is better than the Johnson-like bound. Third, by applying the existing decoding algorithms for Hamming metric and rank metric codes, we present explicit constructions of cover metric codes that can be efficiently list decoded up to the Singleton bound.

Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes C gives decoding radius beyond (1 - R)/2 with positive rate R when the ratio of the number of rows over the number of columns is extremely small, 2) the Johnson bound for rank-metric codes does not exist as opposed to classical codes, and 3) the Gabidulin codes of square matrices cannot be list decoded beyond half of the minimum distance. Although the list decodability of random rank-metric codes and the limits to the list decodability have been determined completely, little work on efficient list decoding of rank-metric codes has been done. The only known efficient list decoding of rank-metric codes C gives decoding radius up to the singleton bound 1-R-e with positive rate R when ρ(C) is extremely small, i.e., O(ε2), where ρ(C) denotes the ratio of the number of rows over the number of columns of C. It is commonly believed that it is difficult to list decode rank-metric codes C with the ratio ρ(C) close to 1. The main purpose of this paper is to explicitly construct a class of rank-metric codes C with the ratio ρ(C) up to 1/2 and efficiently list decode these codes beyond unique decoding radius (1 - R)/2. Furthermore, encoding and list decoding algorithms run in polynomial time poly(n, exp(1/e)). The list size can be reduced to O(1/e) by randomizing the algorithm. Our key idea is to employ bivariate polynomials f (x, y), where f is linearized in variable y and the variable x is used to “fold” the code. In other words, the rows are used to correct rank errors and the columns are used to “fold” the code to enlarge the decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace whose dimension is linear in the number n of columns. This “periodic” structure allows us to pre-encode the messages to prune down the list. More precisely, we use subspace design introduced by Guruswami and Xing to obtain a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced by Guruswami et al. to obtain a randomized algorithm with a smaller constant list size.

Subspace designs are a (large) collection of high-dimensional subspaces {H_i} of F_q^m such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection with W; more precisely, the sum of dimensions of W cap H_i is at most some parameter L. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F^n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log(log(n)))).

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 Mksuch 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.

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance.

Complex orthogonal designs (CODs) are used to construct space-time block codes in wireless transmission. COD Ozwith parameter [p, n, k] is a p × n matrix, where nonzero entries are filled by ±zior ±zi* , i = 1, 2, ..., k, such that equation. In practice, n is the number of antennas, k=p the code rate, and p the decoding delay. One fundamental problem is to construct COD to maximize k/p and minimize p when n is given. Recently, this problem is completely solved by Liang and Adams et al. It's proved that when n = 2m or 2m - 1, the maximal possible rate is (m + 1)/(2m) and the minimum delay (m-12m)(with the only exception n ≡2 (mod 4) where it is 2(m-12m)). However, when the number of antennas increase, the minimum delay grows fast and eats the otherwise fast decoding. For example, when n = 14 the minimal delay for a code with maximal rate is 6006! Therefore, it is very important to study whether it is possible, by lowering the rate slightly, to shorten the decoding delay considerably. In this paper, we demonstrate this possibility by constructing a series of CODs with parameter [p, n, k] = [(w - 1n)+(w + 1n), n, (wn)], where 0 ≤ w ≤ n. Besides that, all optimal CODs, which achieve the maximal rate and minimal delay, are contained in our explicit-form constructions. And this is the first explicit-form construction, while the previous are recursive or algorithmic.