The 12th Korea-Sino International Conference
on Coding Theory and Related Topics

Quasi-cyclic (QC) codes are natural generalizations of cyclic codes that have seen increasing application in recent years to real-life problems. Like for cyclic codes, interesting mathematical tools have been found to be useful in investigations into QC codes. In this talk, we shall discuss some examples of such investigations, and propose some possible directions for further studies.

The error coefficient of a linear code, defined as the number of minimum-weight codewords, plays a central role in evaluating the performance of the code. In this paper, we establish several recursive bounds on the minimum possible error coefficient among optimal linear codes with prescribed parameters. We prove that these bounds are tight in infinitely many cases. Beyond the recursive-bound framework, we determine the minimum possible error coefficient for three explicit families of optimal linear codes: two families arising from simplex codes and one family associated with MacDonald codes.

The I-Ching (Yijing) or Book of Changes (or Joo Yeok in Korean) originated over 3000 years ago in ancient China. It started as a book for telling the future and became a core text for both Confucianism and Taoism. The I-Ching has 64 hexagrams of Yin and Yang. Hence, they correspond to the 6-dimensional space over $\mathbb{F}_2$. Surprisingly, there are not many papers on the mathematical structures of the 64 hexagrams. In this talk, we construct several classes of codes related to the 64 hexagrams from a coding theory viewpoint. We introduce a few open problems in this direction. We do not assume any knowledge of the I-Ching.

In this talk, we study both expansion and embedding of linear codes in both Euclidean and Hermitian hull cases. Firstly we show how to expand Euclidean/Hermitian code to obtain a code with all possible hull dimension. Our results show that every k-dimension code with hull dimension l is contained in a (k + 1)-dimensional code with hull dimension l+1, l or l-1. In particular, for k less than half of n, every [n, k] Euclidean self-orthogonal code is contained in an [n, k + 1] Euclidean self-orthogonal code. Secondly we study the shortest t-dimensional hull embeddings of linear codes in both Euclidean and Hermitian cases. We obtain the exact length of such embeddings by adopting tools from quadratic form theory over finite fields and classical group theory. Finally, applying these algorithms, we provide examples for various settings and obtain several optimal codes inequivalent to those in the BKLC database.

In this talk, we study minimal codewords of linear codes constructed from finite graphs. Minimal codewords are important in coding theory because of their connections with decoding algorithms, secret sharing schemes, and the structural study of linear codes. We first consider codes derived from adjacency matrices of graphs over finite fields, and discuss how graph structures such as common neighbors, triangles, and cycles can be used to construct and count non-equivalent minimal codewords.

We then consider binary linear codes obtained from incidence matrices of simple connected graphs. In this setting, minimal codewords can be described in terms of walks and connected vertex subsets of the underlying graph. By combining these two approaches, we show that graph-theoretic properties provide a useful framework for understanding the structure and enumeration of minimal codewords in graph-based linear codes.

A function $F:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n}$ is defined as $k$-th order sum-free if the sum of its image values over any $k$-dimensional affine subspace $A$ is non-zero, i.e., $\sum\limits_{x\in A}F(x) \neq 0$. This property generalizes the notion of almost perfect nonlinear (APN) functions and holds potential for resisting integral cryptanalysis. The sum-freedom of the multiplicative inverse function over $\mathbb{F}_{2^n}$ has been extensively studied, and its behavior is highly dependent on the parity and prime divisors of $n$. In this talk, we investigate a family of power functions $P_k(x)=x^d$ over the finite field $\mathbb{F}_{2^n}$ with the exponent given by $d=\frac{2^{tk}-1}{2^t-1}$. Under the condition that $\gcd(t,n)=1$, we provide a complete characterization of the sum-freedom of $P_k(x)$. We prove that $P_k(x)$ is $k$-th order sum-free for every $2 \leq k \leq n$, but fails to be sum-free for any order $r$ with $k+1\leq r\leq n$. Additionally, we give the necessary and sufficient conditions for $P_k(x)$ to be first-order sum-free (bijective). We also investigate the differential uniformity of $P_k(x)$ under certain conditions, some of which make $P_k(x)$ APN (second-order sum free). Our results offer new insight into the structural properties of $P_k(x)$ with respect to the notion of sum-freedom.

Strongly regular graphs play an important role in algebraic combinatorics and are closely connected with finite geometry and design theory. A basic problem is to understand which parameter sets of strongly regular graphs can actually occur. In this talk we discuss several results obtained using spectral methods together with structural information about cliques and cocliques. In particular, we explain how eigenvalue constraints interact with large cliques and with cocliques in local graphs, and how these ideas lead to restrictions on the parameters of strongly regular graphs. This is based on joint works with Jack H. Koolen, Chenhui Lv and Greg Markowsky.

In this talk, we investigate the automorphism group of a maximal function field with the second largest possible genus over finite field of even characteristic, which is called the Abdón–Torres function field. As an application, we determine the automorphism groups of one-point algebraic geometry codes from such a maximal function field. It turns out that the automorphism groups of one-point algebraic geometry codes agree with that of the Abdón–Torres function field except for the trivial cases. Moreover, we provide a family of maximal function fields with explicit defining equations via considering fixed subfields with respect to some subgroups of automorphism group of the Abdón–Torres function field.

Let $\mathbb{F}_q$ be the finite field with $q$ elements, and let $n_q(k,d)$ denote the smallest integer $n$ for which there exists an $[n,k,d]_q$ linear code of dimension $k$ and minimum distance $d$. A code attaining the length $n_q(k,d)$ is called a length-optimal code. In this talk, we survey recent progress on length-optimal codes from finite geometry. We discuss the connection between linear codes and geometric structures in projective spaces and present some open problems on $n_q(k,d)$.

The sequence reconstruction problem was first introduced by Levenshtein, addressing how to reconstruct a transmitted codeword based on multiple noisy reads of the codeword. Following Levenshtein's work, most existing research on sequence reconstruction are devoted to the calculation of the reconstruction threshold, i.e., the minimum number of distinct reads required to guarantee unique reconstruction. This problem has gained renewed attentions in recent years due to its application in DNA-based data storage. In this talk, for the substitution channel we introduce a new sufficient condition for sequence reconstruction, along with the corresponding reconstruction algorithms. Our new framework takes both the number of reads and the distances among the reads into consideration. (Joint work with Dr. Chen Wang and Prof. Eitan Yaakobi.)

We propose an amplitude reweighting framework that amplifies candidate states in proportion to the Hamming weight of their feature encodings, so that candidates satisfying more constraints receive proportionally larger amplitudes. The framework combines a weight state constructed via single-qubit rotations with a Hadamard product operation realized via parallel CNOT gates and post-selection. We analyze the post-selection overhead inherent in the Hadamard product implementation and introduce a relaxation parameter and a compensation weighting scheme to consider classical post-processing strategies available under this overhead. Simulations on two Max-Cut instances using Qiskit confirm that the proposed amplitude reweighting increases the detection rate of optimal solutions, and that the compensation weighting scheme restores the target distribution under relaxed post-selection.

This talk mainly focuses on t-designs from the second minimum weights of several classes of NMDS codes. We first establish a correspondence between the codeword of the second minimum weight and some submatrix of the parity check matrix for binary codes and NMDS codes. As an application, we present several infinite families of 3-designs or 2-designs from the codewords of the second minimum weight. Based on the inclusion-exclusion principle, we determine the parameters of these designs by investigating the properties of symmetric polynomials.

In this talk, we mainly investigate profound interconnections between combinatorial designs, linear codes, and Boolean functions. Firstly, we present a generic construction method for designs derived from Boolean functions and give a new concept of non-symmetric designs with the triple symmetric difference property (TSDP). Secondly, we provide an alternative proof for addition designs derived from plateaued functions, which need not be simple or symmetric. We characterize simple $2$-designs on $2^{m-r}$ points arising from $r$-plateaued functions in $m$ variables, and show that addition designs from such functions with no nonzero linear structure satisfy the TSDP but not the double one, yielding non-symmetric simple $2$-designs. Thirdly, we primarily explore the equivalence relationships between designs, linear codes, and plateaued functions. These investigations help resolve two open problems posed by Ding and Tang (Designs from Linear Codes, Singapore: World Scientific, 2022: Problems 14.20, 14.23). We also compute the automorphism groups of addition designs of $r$-plateaued functions and of the linear codes of addition designs. This work extends results by Bending (SDP designs and their automorphism groups, Ph.D. thesis, 1993), and Dempwolff and Neumann (Des. Codes Cryptogr., 57, 373–381, 2010). Finally, we yield new Boolean functions producing two families of a $2$-design whose parameters coincide with those of the complement of a point-hyperplane design and a TSDP design, despite being non-isomorphic. (Joint work with Jieun Kwon, Jiaxin Wang, and Yansheng Wu.)

In coding theory, the weight spectrum, code length, dimension, and minimum distance are recognized as the four most essential and fundamental parameters of a code. Ascertaining the upper and lower bounds on the size of a code's weight spectrum constitutes a foundational problem in this field. This report presents a concise survey of the upper and lower bounds on the size of weight spectra from three distinct perspectives. First, we investigate the bounds for several critically important families of linear codes, including cyclic codes, quasi-cyclic codes, and Reed–Muller codes. Second, we explore the bounds for codes defined over finite rings, where diverse weight metrics are taken into account, such as the Lee weight and the homogeneous weight. Third, we examine the bounds for codes under the symbol-pair metric.

Construction X has been well studied and widely used to construct quantum error-correcting codes. In this paper, we investigate Construction X4, a generalization of Construction X, to construct quantum error-correcting codes from arbitrary linear codes over a finite field of square order. We prove lower bounds on the minimum distance of the resulting quantum codes. For the special case where the classical codes are Hermitian orthogonal, we additionally present two new constructions of quantum codes. Furthermore, as an application, we explore quantum error-correcting codes derived from cyclic codes, Reed-Solomon codes, and generalized Reed-Solomon codes. We report numerous optimal and record breaking quantum codes identified via our theorems.

Combinatorial approaches have played an important role in the study of deletion error-correcting codes. This talk introduces several combinatorial aspects of both classical and quantum deletion codes.

The past few years have witnessed the growing importance of pseudorandom correlation generators (PCGs) for generating correlated randomness with sublinear communication. To date, quasi-linear time PCGs for oblivious linear evaluation (OLE) over arbitrary finite fields have been constructed under either Ring-LPN or Quasi-Abelian syndrome decoding (QA-SD) assumptions, with a throughput of millions of OLEs per second demonstrated, in particular, for the binary field. However, many modern MPC protocols deal with large prime fields, in which existing PCGs suffer from a significant efficiency gap due to a quasi-linear number of multiplications involved in FFT (Fast Fourier Transform) algorithms. Moreover, FFT typically relies on FFT-friendly fields that contain large smooth multiplicative subgroups, and therefore are not well-suited to popular fields, such as Mersenne prime fields.

In this work, we close the gap by leveraging the well-known Walsh-Hadamard transform (WHT) in the context of QA-SD based PCGs. Although WHT is still a quasi-linear time algorithm like normal FFTs, no multiplication is needed — addition and subtraction suffice. Since multiplications over a prime field $\mathbb{F}_p$ typically incur an $O(\log{p})$ overhead over additions, our scheme that avoids a large number of multiplications perfectly fits the large prime field setting. Moreover, we show that with overwhelming probability, the underlying random QA code has a high relative distance, e.g., $0.268$ for rate $1/4$. Experimental results show that WHT is at least one magnitude faster than FFT over a $64$-bit smooth prime field. Consequently, our PCG achieves $27,000$ OLE per second over a $64$-bit prime field. This is the first full implementation of PCG for OLE over an arbitrary large prime field that we are aware of.

We then build PCG for vector-OLE over arbitrary large prime fields from QA-SD assumptions, and fully implement it using the $\mathsf{libOTe}$ library. We achieve a throughput of over $5,000,000$ vector-OLEs per second over a $64$-bit prime field, roughly four times faster than state-of-the-art PCGs from either expand-accumulate (EA) codes (Boyle et al., CRYPTO 2022), or expand-convolute (EC) codes (Raghuraman et al., CRYPTO 2023).

Hermitian Linear Complementary Dual (LCD) codes are an important class of linear codes over finite fields, with connections to quantum error-correcting codes. Constructing Hermitian LCD codes with good parameters remains a challenging problem in coding theory. In this talk, we present a computational approach to constructing quaternary Hermitian LCD codes using modified genetic algorithms. The proposed algorithms are designed as constrained search methods over finite fields, with problem-specific operators adapted to the Hermitian LCD condition. As a result, we obtain more than 100 new inequivalent quaternary Hermitian LCD codes with good minimum distances. (Joint work with Jon-Lark Kim and Yoonjin Lee.)

Codes correcting deletions/insertions have gained a lot of attention due to applications in DNA-based data storage, document exchange, and so on. In this talk, I will report our recent progress on codes correcting bust-deletions and localized deletions.

Let $q$ be an odd prime power and let $\mathbb{F}_q$ be the finite field of order $q$. For a set $A=\{a_1,\dots,a_n\}\subset \mathbb{F}_q$, define \[ h_A(a_i) := \prod_{\substack{1\le j\le n\\ j\ne i}}(a_i-a_j). \] It is known (via generalized Reed–Solomon constructions) that (i) if $n$ is even and $h_A(a_i)$ is a square in $\mathbb{F}_q^\ast$ for all $i$, then there exists a $q$-ary MDS self-dual code of length $n$, and (ii) if $n$ is odd and $-h_A(a_i)$ is a square for all $i$, then there exists a $q$-ary MDS self-dual code of length $n+1$.

This paper strengthens and extends previous results in three directions. First, using an explicit complement formula for $h_A$ together with character sums and the Weil bound, we prove nonexistence results at the extreme sizes $|A|=q-2$ and $|A|=q-3$, and give a general nonexistence theorem. Second, we provide a detailed one-point deletion and addition framework and an infinite family of examples toward an existence–equivalence conjecture. Finally, we prove a full affine transformation law for $h_A$ and its quadratic character, generalizing the scaling symmetry used in earlier work.

There are eleven finite rings of order $p^2$ denoted by $A_p$ to $K_p$ in alphabetical order. In particular, we consider $I_2$ which is a commutative non-unital ring of order 4 defined by generators and relations as \[ I_2 = \left\langle a,b \mid 2a=2b=0,\: a^2=b,\: ab=0 \right\rangle. \] In this talk, we present some maximum distance separable (MDS) codes and additive complementary dual (ACD) codes over the ring $I_2$. We show a relation between ACD codes over $I_2$ and binary linear complementary dual (LCD) codes using a reduction map from $I_2$ to $\mathbb{F}_2$. Using the relation, we classify ACD codes over $I_2$ with the highest minimum distances for small lengths. (Joint work with Jon-Lark Kim and Marvin Olavides, Sogang University.)

Multiple-deletion correction is a fundamental problem in coding theory. Recent work on pointer mapping has established a connection between deletion errors in multiplicity-free sequences and Hamming-metric errors. In this talk, we introduce a new family of non-binary deletion-correcting codes, called pointer codes, based on this framework. The proposed construction achieves a redundancy upper bound of $(8t\log_p n)+O(n)$, which is close to Levenshtein's theoretical lower bound.

We also present an efficient decoding method that reduces deletion correction to classical algebraic decoding techniques, including Euclidean decoding and the Peterson algorithm.

A single coloring channel is defined by a subset of letters it allows to pass through, while deleting all others. A sequence of coloring channels provides multiple views of the same transmitted letter sequence, forming a type of sequence-reconstruction problem useful for protein identification and information storage at the molecular level. In this talk, we provide exact capacities of several sequences of coloring channels: uniform sunflowers, two arbitrary intersecting sets, and paths. We also show how this capacity depends solely on a related graph we define, called the pairs graph. Using this equivalence, we prove lower and upper bounds on the capacity, and a tailored bound for a coloring-channel sequence forming a cycle. In particular, for an alphabet of size 4, these results give the exact capacity of all coloring-channel sequences except for a cycle of length 4, for which we only provide bounds.

In this paper, we introduce twisted Goppa codes, which generalize classical Goppa codes by adding a twisted term. Then we provide an efficient decoding algorithm for twisted Goppa codes. The Niederreiter cryptosystem is bassed on linear error-correcting codes in which the public key is a parity check matrix. When twisted Goppa codes are applied to the Niederreiter cryptosystem, the public key size is overlarge. To reduce the public key size, we construct quasi-cyclic twisted Goppa codes via a non-trivial automorphism group carefully selecting the defining set and the matched polynomial. Moreover, we obtain a family of cyclic twisted Goppa codes.

Let $q$ be an even power of a prime number $p$. Let $\mathbb{F}_q$ be the finite field with $q$ elements, and $\mathbb{P}^2(\mathbb{F}_q)$ the projective plane over $\mathbb{F}_q$. We denote by $\mathbb{F}_{\sqrt{q}}$ and $\overline{\mathbb{F}}_q$ the subfield with $\sqrt{q}$ elements and the algebraic closure of $\mathbb{F}_q$, respectively.

For $A \in \mathrm{GL}(3,\mathbb{F}_q)$, $C_A$ denotes the plane curve defined by $(x^{\sqrt{q}}, y^{\sqrt{q}}, z^{\sqrt{q}})\,A\,(x,y,z)^t = 0$. We call $C_A$ a relative of the Hermitian curve (or, more briefly, a Hermitian-relative curve). Let $A^{\ast}$ be the matrix obtained by taking the entrywise $\sqrt{q}$-th power of $A$ and transposing it. Then $C_A$ is a Hermitian curve if $A = A^{\ast}$, which is an important curve in characteristic $p > 0$ for various reasons.

In this talk, we show that any Hermitian-relative curve over $\mathbb{F}_q$ with $q > 4$ is of type $(n,i) \in \{(q\sqrt{q}+1,\, q\sqrt{q}+1),\ (\sqrt{q}+1,\, \sqrt{q}+1),\ (1,1),\ (q-\sqrt{q}+1,\, 0),\ (q+1,1),\ (q+1,2),\ (q+\sqrt{q}+1,1),\ (q+2\sqrt{q}+1,0)\}$, where $n$ and $i$ denote the number of $\mathbb{F}_q$-points and the number of inflexions of $C_A$, respectively. Conversely, for any $(n,i)$ in this set, there exists a curve of type $(n,i)$.

(Joint work with Masaaki Homma.)