2021 年代数几何码研讨会（Ⅱ）日程表
时间：12/1112/16
Zoom 会议号：396 431 7007 密码：579229
（注：6 天同一会议号及密码）
12 月 11 号 会议时间：9:0017:30  
早餐（一号食堂二楼）7：009：00  
时间 
主持人 
报告人 
报告题目 
9:009:45 
冯克勤 
邢朝平 
Progress Report on the Project of Algebraic Geometry Codes 
9:4510:30 
马立明 
An Introduction to Algebraic Geometry Codes(I) 

10:3011:00 
茶歇 

11:0011:45 
马立明 
An Introduction to Algebraic Geometry Codes(II) 

午餐（湖滨食堂二楼）  
14:3017:30 
自由讨论交流 

晚宴（奥林宾馆）  
12 月 12 号 会议时间：9:0017:30  
早餐（一号食堂二楼）7：009：00  
时间 
主持人 
报告人 
报告题目 
9:009:45 
邢朝平 
上官冲 
Combinatorial ListDecoding of ReedSolomon Codes 
9:4510:30 
Masahito Hayashi 
Secure list decoding and its application to bitstring commitment 

10:3011:30 
茶歇 

11:0011:45 
胡创强 
Drinfeld Modular Curves Arising from TTorsion Trees and Their Applications in AG Codes 

午餐（湖滨食堂二楼）  
14:3017:30 
自由讨论交流 

晚餐（湖滨食堂二楼）  
12 月 13 号 会议时间：9:0017:30  
早餐（一号食堂二楼）7：009：00  
时间 
主持人 
报告人 
报告题目 
9:009:45 
向青 
张子涵 
A Survey on the Decoding of AlgebraicGeometry Codes(I) 
9:4510:30 
张子涵 
A Survey on the Decoding of AlgebraicGeometry Codes(II) 

10:3011:00 
茶歇 

11:0011:45 
彭帆 
Decoding Algebraic Geometry Codes up to
d∗−1 2 

午餐（湖滨食堂二楼）  
14:3017:30 
自由讨论交流 
晚餐（湖滨食堂二楼）  
12 月 14 号 会议时间：9:0017:30  
自由交流  
12 月 15 号 会议时间：9:0017:30  
早餐（一号食堂二楼）7：009：00  
时间 
主持人 
报告人 
报告题目 
9:009:45 
李才恒 
韩永祥 
Update Bandwidth for Distributed Storage 
9:4510:30 
曹喜望 
Constructions of Optimal Binary Locally Recoverable Codes via a General Construction of Linear Codes 

10:3011:00 
茶歇 

11:0011:45 
刘姝 
Maximally Recoverable Local Reconstruction Codes from Subspace Direct Sum Systems 

午餐（湖滨食堂二楼）  
14:3017:30 
自由讨论交流 

晚餐（湖滨食堂二楼）  
12 月 16 号 会议时间：9:0017:30  
早餐（一号食堂二楼）7：009：00 
时间 
主持人 
报告人 
报告题目 
8:459:30 
曹喜望 
袁晨 
On the Complexity of Arithmetic Secret Sharing 
9:3010:15 
王琦 
On the size distribution of Levenshtein balls with radius one 

10:1510:30 
茶歇 

10:3011:15 
张俊 
ReedSolomon 码深洞问题的最新进展 

11:1512:00 
肖东亮 
一种改进的代数几何码构造算法研究 

午餐（湖滨食堂二楼）  
14:3017:30 
自由讨论交流 

晚餐（湖滨食堂二楼）  
12 月 17 号  
早餐（一号食堂二楼）7：009：00 
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 closedform 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 MRMUB 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 MRMUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MRMUB codes.
Drinfeld Modular Curves Arising from TTorsion Trees and Their Applications in AG Codes
胡创强
（北京雁栖湖应用数学研究院，北京）
Drinfeld modular curves are used to construct sequences of curves with many rational points over any nonprime 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 errorcorrection 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 rank2 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 Ttorsion tree. We believe that our novel approach by the Ttorsion 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^{h1o(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^{h2+\frac1{h1}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 longstanding benchmark bound, the GilbertVarshamov 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 TafasmanVladutZink bound.
Decoding Algebraic Geometry Codes up to
彭帆
（广西师范大学，桂林）
FengRao 在1993年提出通用的多数决议译码算法，是第一个可纠正个错误的译码算法复杂度为O().而相对简单的BerlekampWelch算法可以纠正个错误.1999年GuruswamiSudan应用带重数对带权重的高阶二元多项式插值并求根，将BW算法推广到代数几何的listdecoding.借鉴GuruswamiSudan 译码的插值部分，我们提出了一个可以纠正个错误的通用代数几何码译码算法.再应用多项式格(Lattices on polynomial rings)上的快速基约化(base reduction)算法，可将Hermitian码的译码复杂度降低到O().
Combinatorial ListDecoding of ReedSolomon Codes
上官冲
（山东大学，青岛）
The notion of listdecoding 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 listdecoding is measured by its listdecoding radius. It is wellknown that the listdecoding radius of any given code lies between the Johnson bound and the listdecoding capacity. It is also wellknown that random codes achieve listdecoding capacity with high probability. However, until recently, it had been a longstanding open question that whether ReedSolomon codes can be listdecoded beyond the Johnson radius. In this talk, we will survey the known results on the listdecoding radius of ReedSolomon 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, BarLev, 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 ReedSolomon 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, asymptoticallygood stronglymultiplicative linear (ramp) secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constantcommunicationrate results in multiparty cryptographic scenarios, and, surprisingly, in twoparty 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 wellknown 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 quasilinear 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.
ReedSolomon码深洞问题的最新进展
张俊
（首都师范大学，北京）
报告中，我们讨论ReedSolomon码深洞问题和一类有限几何问题的联系,首先我们将所找到的深洞的描述为特殊的几何对象；再通过有限几何的方法，构造出更多的深洞。
A Survey on the Decoding of AlgebraicGeometry Codes
张子涵
（上海交通大学，上海）
In this talk, we give an overview on the development of decoding AlgebraicGeometry codes. We will give a brief introductions on several major decoding algorithms including BerlekampWelch type algorithm, FengRao’s majority voting algorithm, BerlekampMassey type algorithm, power decoding algorithm and GuruswamiSudan type list decoding algorithm etc. Meanwhile, we will give the computational complexity of those aforementioned algorithms and conclude the bestknown ones as well.