Source author record

Lingfei Jin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Discrete Mathematics math.AG quant-ph

Catalog footprint

Research overview

11works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Efficient Decoding of Twisted GRS Codes and Roth--Lempel Codes

MDS codes play a central role in practice due to their broad applications. To date, most known MDS codes are generalized Reed-Solomon (GRS) codes, leaving codes that are not equivalent to GRS codes comparatively less understood. Studying this non-GRS regime is therefore of intrinsic theoretical interest, and is also practically relevant since the strong algebraic structure of GRS codes can be undesirable in cryptographic settings. Among the known non-GRS codes, twisted generalized Reed-Solomon (TGRS) codes and Roth-Lempel codes are two representative families of non-GRS codes that have attracted significant attention. Though substantial work has been devoted to the construction and structural analysis of TGRS and Roth-Lempel codes, comparatively little attention has been paid to their decoding, and many problems remain open. In this paper, we propose list and unique decoding algorithms for TGRS codes and Roth-Lempel codes based on the Guruswami-Sudan algorithm. Under suitable parameter conditions, our algorithms achieve near-linear running time in the code length, improving upon the previously best-known quadratic-time complexity. Our TGRS decoder supports fixed-rate TGRS codes with up to O(n^2) twists, substantially extending prior work that only handled the single-twist case. For Roth-Lempel codes, we provide what appears to be the first efficient decoder. Moreover, our list decoders surpass the classical unique-decoding radius for a broad range of parameters. Finally, we incorporate algebraic manipulation detection (AMD) codes into the list-decoding framework, enabling recovery of the correct message from the output list with high probability.

preprint2020arXiv

A Construction of New Quantum MDS Codes

It has been a great challenge to construct new quantum MDS codes. In particular, it is very hard to construct quantum MDS codes with relatively large minimum distance. So far, except for some sparse lengths, all known $q$ -ary quantum MDS codes have minimum distance less than or equal to $q/2+1$ . In the present paper, we provide a construction of quantum MDS codes with minimum distance bigger than $q/2+1$ . In particular, we show existence of $q$ -ary quantum MDS codes with length $n=q^2+1$ and minimum distance $d$ for any $d\le q-1$ and $d= q+1$ (this result extends those given in \cite{Gu11,Jin1,KZ12}); and with length $(q^2+2)/3$ and minimum distance $d$ for any $d\le (2q+2)/3$ if $3|(q+1)$ . Our method is through Hermitian self-orthogonal codes. The main idea of constructing Hermitian self-orthogonal codes is based on the solvability in $\F_q$ of a system of homogenous equations over $\F_{q^2}$.

preprint2020arXiv

Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes

It was shown in \cite{GXY18} that the length $n$ of a $q$ -ary linear locally recoverable code with distance $d\ge 5$ is upper bounded by $O(dq^3)$ . Thus, it is a challenging problem to construct $q$ -ary locally recoverable codes with distance $d\ge 5$ and length approaching the upper bound. The paper \cite{GXY18} also gave an algorithmic construction of $q$ -ary locally recoverable codes with locality $r$ and length $n=Ω_r(q^2)$ for $d=5$ and $6$ , where $Ω_r$ means that the implicit constant depends on locality $r$ . In the present paper, we present an explicit construction of $q$ -ary locally recoverable codes of distance $d= 5$ and $6$ via binary constant weight codes. It turns out that (i) our construction is simpler and more explicit; and (ii) lengths of our codes are larger than those given in \cite{GXY18}.

preprint2016arXiv

New MDS Self-Dual Codes from Generalized Reed-Solomon Codes

Both MDS and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining existence of $q$ -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where $q$ is even. The current paper focuses on the case where $q$ is odd. We construct a few classes of new MDS self-dual code through generalized Reed-Solomon codes. More precisely, we show that for any given even length $n$ we have a $q$ -ary MDS code as long as $q\equiv1\bmod{4}$ and $q$ is sufficiently large (say $q\ge 2^n\times n^2)$ . Furthermore, we prove that there exists a $q$ -ary MDS self-dual code of length $n$ if $q=r^2$ and $n$ satisfies one of the three conditions: (i) $n\le r$ and $n$ is even; (ii) $q$ is odd and $n-1$ is an odd divisor of $q-1$ ; (iii) $r\equiv3\mod{4}$ and $n=2tr$ for any $t\le (r-1)/2$ .

preprint2016arXiv

On the List-Decodability of Random Self-Orthogonal Codes

In 2011, Guruswami-Håstad-Kopparty \cite{Gru} showed that the list-decodability of random linear codes is as good as that of general random codes. In the present paper, we further strengthen the result by showing that the list-decodability of random {\it Euclidean self-orthogonal} codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. Specifically, we show that, for any fixed finite field $\F_q$, error fraction $δ\in (0,1-1/q)$ satisfying $1-H_q(δ)\le \frac12$ and small $ε>0$ , with high probability a random Euclidean self-orthogonal code over $\F_q$ of rate $1-H_q(δ)-ε$ is $(δ, O(1/ε))$ -list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding {\it symplectic dual-containing} codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.

preprint2015arXiv

Multipartite entangled states, symmetric matrices and error-correcting codes

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 classical error-correcting codes. There are three main results arising from our constructions. Firstly, we show that for any given even $n\ge 2$ , there always exists an $n/2$ -uniform $n$ -qudit quantum state of level $p$ for sufficiently large prime $p$ . Secondly, both constructions show that their 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 outperforms the one by error-correcting codes. Thirdly, our symmetric matrix construction provides a positive answer to the open question in \cite{DA} on whether there exists $3$ -uniform $n$ -qudit pure quantum state for all $n\ge 8$ . In fact, we can further prove that, for every $k$ , there exists a constant $M_k$ such that there exists a $k$ -uniform $n$ -qudit quantum state for all $n\ge M_k$ . In addition, by using concatenation of algebraic geometry codes, we give an explicit construction of $k$ -uniform quantum state when $k$ tends to infinity.

preprint2014arXiv

Erasure List-Decodable Codes from Random and Algebraic Geometry Codes

Erasure list decoding was introduced to correct a larger number of erasures with output of a list of possible candidates. In the present paper, we consider both random linear codes and algebraic geometry codes for list decoding erasure errors. The contributions of this paper are two-fold. Firstly, we show that, for arbitrary $0<R<1$ and $ε>0$ ( $R$ and $ε$ are independent), with high probability a random linear code is an erasure list decodable code with constant list size $2^{O(1/ε)}$ that can correct a fraction $1-R-ε$ of erasures, i.e., a random linear code achieves the information-theoretic optimal trade-off between information rate and fraction of erasure errors. Secondly, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, for any $0<R<1$ and $ε>0$ , a $q$ -ary algebraic geometry code of rate $R$ from the Garcia-Stichtenoth tower can correct $1-R-\frac{1}{\sqrt{q}-1}+\frac{1}{q}-ε$ fraction of erasure errors with list size $O(1/ε)$ . This improves the Johnson bound applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time.

preprint2013arXiv

A Construction of Quantum Codes via A Class of Classical Polynomial Codes

There have been various constructions of classical codes from polynomial valuations in literature \cite{ARC04, LNX01,LX04,XF04,XL00}. In this paper, we present a construction of classical codes based on polynomial construction again. One of the features of this construction is that not only the classical codes arisen from the construction have good parameters, but also quantum codes with reasonably good parameters can be produced from these classical codes. In particular, some new quantum codes are constructed (see Examples \ref{5.5} and \ref{5.6}).

preprint2013arXiv

Euclidean and Hermitian Self-orthogonal Algebraic Geometry Codes and Their Application to Quantum Codes

In the present paper, we show that if the dimension of an arbitrary algebraic geometry code over a finite field of even characters is slightly less than half of its length, then it is equivalent to an Euclidean self-orthogonal code. However, in the literatures, a strong contrition about existence of certain differential is required to obtain such a result. We also show a similar result on Hermitian self-orthogonal algebraic geometry codes. As a consequence, we can apply our result to quantum codes and obtain quantum codes with good asymptotic bounds.

preprint2013arXiv

Quantum Gilbert-Varshamov Bound Through Symplectic Self-Orthogonal Codes

It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov bound for quantum codes. The idea of obtaining the Gilbert-Varshamov bound for symplectic self-orthogonal codes follows from counting arguments.

preprint2013arXiv

Quantum Stabilizer Codes from Maximal Curves

A curve attaining the Hasse-Weil bound is called a maximal curve. Usually classical error-correcting codes obtained from a maximal curve have good parameters. However, the quantum stabilizer codes obtained from such classical error-correcting codes via Euclidean or Hermitian self-orthogonality do not always possess good parameters. In this paper, the Hermitian self-orthogonality of algebraic geometry codes obtained from two maximal curves is investigated. It turns out that the stabilizer quantum codes produced from such Hermitian self-orthogonal classical codes have good parameters.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Lingfei Jin

Research overview

Is this your work?

11 publications

Efficient Decoding of Twisted GRS Codes and Roth--Lempel Codes

A Construction of New Quantum MDS Codes

Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes

New MDS Self-Dual Codes from Generalized Reed-Solomon Codes

On the List-Decodability of Random Self-Orthogonal Codes

Multipartite entangled states, symmetric matrices and error-correcting codes

Erasure List-Decodable Codes from Random and Algebraic Geometry Codes

A Construction of Quantum Codes via A Class of Classical Polynomial Codes

Euclidean and Hermitian Self-orthogonal Algebraic Geometry Codes and Their Application to Quantum Codes

Quantum Gilbert-Varshamov Bound Through Symplectic Self-Orthogonal Codes

Quantum Stabilizer Codes from Maximal Curves

See the researcher in context

Building this map preview