2021 年代数几何码研讨会（Ⅱ）日程表

时间：12/11-12/16

Zoom 会议号：396 431 7007  密码：579229

（注：6 天同一会议号及密码）

Constructions of Optimal Binary Locally Recoverable Codes via a General Construction of Linear Codes

曹喜望

（南京航空航天大学，南京）

Locally recoverable codes play a crucial role in distributed storage systems. Many studies have only focused on the constructions of optimal locally recoverable codes with regard to the Singleton bound. In this talk, we will introduce some new frameworks for constructing optimal binary locally recoverable codes meeting the alphabet dependent bound. Using a general framework for linear codes associated to a set, we provide a new approach to constructing binary locally recoverable codes with locality 2. We turn the problem of designing optimal binary locally recoverable codes into constructing a suitable set. Several constructions of optimal binary locally recoverable codes are proposed by this new method. Finally, we propose constructions of optimal binary locally recoverable codes with locality 2 and locality parameters ($(r,\delta)$) by Griesmer codes.  

Update Bandwidth for Distributed Storage

韩永祥

（电子科技大学，深圳）

In this talk, we consider the update bandwidth in distributed storage systems~(DSSs). The update bandwidth, which measures the transmission efficiency of the update process in DSSs, is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated. This talk contains the following contributions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth~(MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irregular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code redundancy and the minimum update bandwidth. Last, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes.

Drinfeld Modular Curves Arising from T-Torsion Trees and Their Applications in AG Codes

胡创强

（北京雁栖湖应用数学研究院，北京）

Drinfeld modular curves are used to construct sequences of curves with many rational points over any non-prime field. The specific structure of Drinfeld modular curve plays an important role in the field of coding. Indeed, constructing a linear error correction code with a sufficiently long code length is a fundamental problem in coding theory. In the 1980s, V.D.Goppa used the algebraic curve over finite fields to construct a special linear error correction code, which is now called the algebraic geometry code. The parameters (code length, dimension, minimum Hamming distance) of this type of linear code mainly depend on the geometric properties of the corresponding algebraic curve, namely, the number of rational points and genus. It is proved theoretically that there is a family of asymptotically optimal linear error-correction codes whose parameters attain the Drinfeld–Vladut bound. Surprisingly, in 1982, Tsfasman, Vladut¸, and Zink proved the existence of an asymptotically optimal long linear code with relative parameters which exceeds the Gilbert–Varshamov bound within a certain range. This work shows a vital link between Ihara’s quantity and the realm of coding theory. In practical applications, we need to know the explicit construction of such algebraic geometry codes, and it boils down to finding a family of asymptotically good function field sequences (called tower) which are measured by the Ihara’s constant. In 2000, based on his procedure for constructing explicit towers of modular curves, Elkies deduced explicit equations of rank-2 Drinfeld modular curves which coincide with the asymptotically optimal towers of curves constructed by Garcia and Stichtenoth. In 2015, Bassa, Beelen, Garcia, and Stichtenoth constructed a celebrated (recursive and good) tower (BBGS tower for short) of curves and outlined a modular interpretation of the defining equations. In this talk, we aim to construct a sequence of Drinfeld modular curves which are organized in an elegant manner — a hierarchical topology tree which we call the T-torsion tree. We believe that our novel approach by the T-torsion tree not only promotes the classic torsion sequence structure, but also further integrates the internal connections of different torsion structures.

Maximally Recoverable Local Reconstruction Codes from Subspace Direct Sum Systems

刘姝

（电子科技大学，成都）

Maximally recoverable local reconstruction codes (MR LRCs for short) have received great attention in the last few years. Various constructions have been proposed in literatures. The main focus of this topic is to construct MR LRCs over small fields. An $(N=nr,r,h,\Gd)$-MR LRC is a linear code over finite field $\F_\ell$ of length $N$, whose codeword symbols are partitioned into $n$ local groups each of size $r$. Each local group can repair any $\Gd$ erasure errors and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns.

MR LRCs deployed in practice have a small number of global parities such as $h=O(1)$. In this parameter setting, all previous constructions require the field size $\ell =\Omega_h (N^{h-1-o(1)})$. It remains challenging to improve this  bound. In this paper, via subspace direct sum systems, we present a construction of MR LRC with the field size $\ell= O(N^{h-2+\frac1{h-1}-o(1)})$. In particular, for the most interesting cases where $h=2,3$, we improve previous constructions by either reducing field size or removing constraints. In addition, we also offer some constructions of MR LRCs for larger global parity $h$ that have field size incomparable with known upper bounds. The main techniques used in this paper is through subspace direct sum systems that we introduce. Interestingly, subspace direct sum systems are actually equivalent to $\F_q$-linear codes over extension fields. Based on various constructions of subspace direct sum systems, we are able to construct several classes of MR LRCs. 

An Introduction to Algebraic Geometry Codes

马立明

（中国科学技术大学，合肥）

 In this talk, I will present a brief introduction to algebraic geometry codes. The discovery of algebraic geometry codes by Goppa has greatly stimulated research in both coding theory and number theory. The major breakthrough of Goppa’s algebraic geometric codes is that they improved the long-standing benchmark bound, the Gilbert-Varshamov bound (GV bound for short).

In this talk, I will introduce the basic concepts and theory of algebraic function fields over finite fields in the first part, various constructions of algebraic geometry codes in the section part, and asymptotic construction of algebraic geometry codes exceeding the GV bound in the third part. In particular, I will focus on the asymptotic constructions of algebraic geometry codes exceeding the GV bound or Tafasman-Vladut-Zink bound.

Decoding Algebraic Geometry Codes up to 

彭帆

                                     （广西师范大学，桂林）                                                                   

     Feng-Rao 在1993年提出通用的多数决议译码算法，是第一个可纠正个错误的译码算法复杂度为O().而相对简单的Berlekamp-Welch算法可以纠正个错误.1999年Guruswami-Sudan应用带重数对带权重的高阶二元多项式插值并求根，将BW算法推广到代数几何的list-decoding.借鉴Guruswami-Sudan 译码的插值部分，我们提出了一个可以纠正个错误的通用代数几何码译码算法.再应用多项式格(Lattices on polynomial rings)上的快速基约化(base reduction)算法，可将Hermitian码的译码复杂度降低到O(). 

Combinatorial List-Decoding of Reed-Solomon Codes

上官冲

（山东大学，青岛）

The notion of list-decoding was introduced independently by Elias and Wozencraft in the 1950s. It is a generalization of the unique decoding model typically considered in coding theory, where given a received word the decoder might output a list of possible codewords, instead of a unique one. This allows for handling a greater number of errors than that allowed by unique decoding.

The number of errors that can be handled by a given code in list-decoding is measured by its list-decoding radius. It is well-known that the list-decoding radius of any given code lies between the Johnson bound and the list-decoding capacity. It is also well-known that random codes achieve list-decoding capacity with high probability. However, until recently, it had been a longstanding open question that whether Reed-Solomon codes can be list-decoded beyond the Johnson radius. In this talk, we will survey the known results on the list-decoding radius of Reed-Solomon codes, and show how polynomial method and graph theory come into play in the recent study of this topic.

On the size distribution of Levenshtein balls with radius one

王琦

（南方科技大学，深圳）

The fixed length Levenshtein (FLL) distance between two words $\mathbf{x, y} \in \mathbb{Z}_m^n$ is the smallest integer $t$ such that the word $\mathbf{x}$ can be transferred to $\mathbf{y}$ by $t$ insertions and $t$ deletions. The size of a ball in FLL metric is a fundamental but challenging problem. Very recently, Bar-Lev, Etzion, and Yaakobi found the explicit expressions for the minimum, maximum and average sizes of FLL balls with radius one. In this talk, we will further prove that the size of the FLL ball with radius one is highly concentrated around its mean by Azuma's inequality.

一种改进的代数几何码构造算法研究

肖东亮

（中国农业大学，北京）

    基于伴随式计算差错位置多项式的译码算法提出了一种改进方法，达到了代数几何码的设计纠错能力，通过仿真测试，与当前主流编码技术LDPC码和Polar码进行了比较，以软判决译码算法为代表的LDPC码在低信噪比环境下具有优势，而由于代数几何码良好的距离特性将在高信噪比条件下纠错性能超过LDPC码，降低了误码平底。针对低信噪比环境的要求，提出了代数几何码和LDPC码级联方案，性能提升显著。根据随机共振机理，还提出了一种加扰算法。 

Progress Report on the Project of Algebraic Geometry Codes

邢朝平

（上海交通大学，上海）

In this talk, we will first survey some results on Reed-Solomon codes as well as algebraic geometry codes. We will then report some of our recent progresses on constructions of algebraic geometry codes and decoding of algebraic geometry codes. Finally, some possible research goals on algebraic geometry codes are proposed.

On the Complexity of Arithmetic Secret Sharing

袁晨

（上海交通大学，上海）

Since the mid 2000s, asymptotically-good strongly-multiplicative linear (ramp) secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constant-communication-rate results in multi-party cryptographic scenarios, and, surprisingly, in two-party cryptography as well.

Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes appeared in CRYPTO 2006 whether the use of “heavy machinery” can be avoided here. i.e., the question is whether the mere existence of such schemes can also be proved by “elementary” techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.

In this talk, we show the theoretical result that, (1) no matter whether this open question has an affirmative answer or not, these schemes can be constructed explicitly by elementary algorithms defined in terms of basic algebraic coding theory. This pertains to all relevant operations associated to such schemes, including, notably, the generation of an instance for a given number of players n, as well as error correction in the presence of corrupt shares. We further show that (2) the algorithms are quasi-linear time (in n); this is (asymptotically) significantly more efficient than the known constructions. That said, the analysis of the mere termination of these algorithms does still rely on algebraic geometry, in the sense that it requires blackbox application of suitable existence results for these schemes. This is a joint work with Ronald Cramer and Chaoping Xing.

Reed-Solomon码深洞问题的最新进展

张俊

（首都师范大学，北京）

报告中，我们讨论Reed-Solomon码深洞问题和一类有限几何问题的联系,首先我们将所找到的深洞的描述为特殊的几何对象；再通过有限几何的方法，构造出更多的深洞。

A Survey on the Decoding of Algebraic-Geometry Codes

张子涵

（上海交通大学，上海）

In this talk, we give an overview on the development of decoding Algebraic-Geometry codes. We will give a brief introductions on several major decoding algorithms including Berlekamp-Welch type algorithm, Feng-Rao’s majority voting algorithm, Berlekamp-Massey type algorithm, power decoding algorithm and Guruswami-Sudan type list decoding algorithm etc. Meanwhile, we will give the computational complexity of those aforementioned algorithms and conclude the best-known ones as well.