BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in O~(s2ℓω−1μω−1(n+g)+ℓωμω) operations in the underlying finite field, where n is the code length, g is the genus of the function field used to construct the code, s is the multiplicity parameter, ℓ is the designed list size and μ is the smallest positive element in the Weierstrass semigroup of some chosen place.
We give a complete conjectural formula for the number er(d,m) of maximum possible Fq-rational points on a projective algebraic variety defined by r linearly independent homogeneous polynomial equations of degree d in m+1 variables with coefficients in the finite field Fq with q elements, when d<q. It is shown that this formula holds in the affirmative for several values of r. In the general case, we give explicit lower and upper bounds for er(d,m) and show that they are sometimes attained. Our approach uses a relatively recent result, called the projective footprint bound, together with results from extremal combinatorics such as the Clements-Lindström Theorem and its variants. Applications to the problem of determining the generalized Hamming weights of projective Reed-Muller codes are also included.
Since Serre gave his famous Harvard lectures in 1985 on various aspects of the theory of algebraic curves defined over a finite field, there have been many developments. In this survey article, an overview will be given on the developments concerning the quantity A(q), known as Ihara's constant. The main focus will be on explicit techniques and in particular recursively defined towers of function fields over a finite field, which have given good lower bounds for Ihara's constant in the past.
We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using O~(sℓωμω−1(n+g)) operations in the underlying finite field, where n is the code length, g is the genus of the function field used to construct the code, s is the multiplicity parameter, ℓ is the designed list size and μ is the smallest positive element in the Weierstrass semigroup at some chosen place; the "soft-O" notation O~(⋅) is similar to the "big-O" notation O(⋅), but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.
Let X be a projective, irreducible, nonsingular algebraic curve over the finite field Fq with q elements and let ∣X(Fq)∣ and g(X) be its number of rational points and genus respectively. The Ihara constant A(q) has been intensively studied during the last decades, and it is defined as the limit superior of ∣X(Fq)∣/g(X) as the genus of X goes to infinity. In 2012 Homma defined an analogue D(q) of A(q), where the nonsingularity of X is dropped and g(X) is replaced with the degree of X. We will call D(q) Homma's constant. In this paper, upper and lower bounds for the value of D(q) are found.
In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed-Solomon codes. Whereas Reed-Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.
For a non-degenerate irreducible curve C of degree d in P3 over Fq, we prove that the number Nq(C) of Fq-rational points of C satisfies the inequality Nq(C)≤(d−2)q+1. Our result improves the previous bound Nq(C)≤(d−1)q+1 obtained by Homma in 2012 and leads to a natural conjecture generalizing Sziklai's bound for the number of points of plane curves over finite fields.
In this article we prove a conjecture formulated by A.B. Soerensen in 1991 on the maximal number of Fq2-rational points on the intersection of a non-degenerate Hermitian surface and a surface of degree d≤q.
We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called Cab curves, as well as algorithms for inverting the encoding map, which we call "unencoding". Some Cab curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity O~(n3/2) resp. O~(qn) for AG codes over any Cab curve satisfying very mild assumptions, where n is the code length and q the base field size, and O~ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, notably the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity O~(n) for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse--Weil bound, our encoding algorithm has complexity O~(n5/4) while unencoding has O~(n3/2).
In 1991 Sørensen proposed a conjecture for the maximum number of points on the intersection of a surface of degree d and a non-degenerate Hermitian surface in $\PP^3(\Fqt)$. The conjecture was proven to be true by Edoukou in the case when d=2. In this paper, we prove that the conjecture is true for d=3 and q≥8. We further determine the second highest number of rational points on the intersection of a cubic surface and a non-degenerate Hermitian surface. Finally, we classify all the cubic surfaces that admit the highest and second highest number of points in common with a non-degenerate Hermitian surface. This classifications disproves one of the conjectures proposed by Edoukou, Ling and Xing.
In this article, we consider the decoding problem of Grassmann codes using majority logic. We show that for two points of the Grassmannian, there exists a canonical path between these points once a complete flag is fixed. These paths are used to construct a large set of parity checks orthogonal on a coordinate of the code, resulting in a majority decoding algorithm.
In 2017, D. Skabelund constructed a maximal curve over Fq4 as a cyclic cover of the Suzuki curve. In this paper we explicitly determine the structure of the Weierstrass semigroup at any point P of the Skabelund curve. We show that its Weierstrass points are precisely the Fq4-rational points. Also we show that among the Weierstrass points, two types of Weierstrass semigroup occur: one for the Fq-rational points, one for the remaining Fq4-rational points. For each of these two types its Apéry set is computed as well as a set of generators.
We give a complete characterization of all Galois subfields of the generalized Giulietti--Korchmáros function fields $\mathcal C_n / \fqn$ for n≥5. Calculating the genera of the corresponding fixed fields, we find new additions to the list of known genera of maximal function fields.
In this article we give a Drinfeld modular interpretation for various towers of function fields meeting Zink's bound.
In this article we count the number of generalized Reed-Solomon (GRS) codes of dimension k and length n, including the codes coming from a non-degenerate conic plus nucleus. We compare our results with known formulae for the number of 3-dimensional MDS codes of length n=6,7,8,9.
In this paper we investigate examples of good and optimal Drinfeld modular towers of function fields. Surprisingly, the optimality of these towers has not been investigated in full detail in the literature. We also give an algorithmic approach on how to obtain explicit defining equations for some of these towers and in particular give a new explicit example of an optimal tower over a quadratic finite field.
We consider a class of linear codes associated to projective algebraic varieties defined by the vanishing of minors of a fixed size of a generic matrix. It is seen that the resulting code has only a small number of distinct weights. The case of varieties defined by the vanishing of 2 x 2 minors is considered in some detail. Here we obtain the complete weight distribution. Moreover, several generalized Hamming weights are determined explicitly and it is shown that the first few of them coincide with the distinct nonzero weights. One of the tools used is to determine the maximum possible number of matrices of rank 1 in a linear space of matrices of a given dimension over a finite field. In particular, we determine the structure and the maximum possible dimension of linear spaces of matrices in which every nonzero matrix has rank 1.
We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realisation of the Guruswami-Sudan algorithm by using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimisation. The second is a Power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the same methods from computer algebra, yielding similar asymptotic complexities.
In this paper we construct Galois towers with good asymptotic properties over any non-prime finite field Fℓ; i.e., we construct sequences of function fields N=(N1⊂N2⊂⋯) over Fℓ of increasing genus, such that all the extensions Ni/N1 are Galois extensions and the number of rational places of these function fields grows linearly with the genus. The limits of the towers satisfy the same lower bounds as the best currently known lower bounds for the Ihara constant for non-prime finite fields. Towers with these properties are important for applications in various fields including coding theory and cryptography.
In this paper, we will give an overview of known and new techniques on how one can obtain explicit equations for candidates of good towers of function fields. The techniques are founded in modular theory (both the classical modular theory and the Drinfeld modular theory). In the classical modular setup, optimal towers can be obtained, while in the Drinfeld modular setup, good towers over any non-prime field may be found. We illustrate the theory with several examples, thus explaining some known towers as well as giving new examples of good explicitly defined towers of function fields.
We derive the Wu list-decoding algorithm for Generalised Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm (EA) as the initial algorithm instead of the Berlekamp-Massey algorithm (BMA). We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm (GSA), immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.
Over all non-prime finite fields, we construct some recursive towers of function fields with many rational places. Thus we obtain a substantial improvement on all known lower bounds for Ihara's quantity A(ℓ), for ℓ=pn with p prime and n>3 odd. We relate the explicit equations to Drinfeld modular varieties.
In this paper we give a closed form expression for the Drinfeld modular polynomial ΦT(X,Y)∈Fq(T)[X,Y] for arbitrary q and prove a conjecture of Schweizer. A new identity involving the Catalan numbers plays a central role.
In this article we use techniques from coding theory to derive upper bounds for the number of rational places of the function field of an algebraic curve defined over a finite field. The used techniques yield upper bounds if the (generalized) Weierstrass semigroup [P. Beelen, N. Tutaş: A generalization of the Weierstrass semigroup, J. Pure Appl. Algebra, 207(2), 2006] for an n-tuple of places is known, even if the exact defining equation of the curve is not known. As shown in examples, this sometimes enables one to get an upper bound for the number of rational places for families of function fields. Our results extend results in [O. Geil, R. Matsumoto: Bounding the number of Fq-rational places in algebraic function fields using Weierstrass semigroups. Pure Appl. Algebra, 213(6), 2009].
Affine Grassmann codes are a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. These codes were introduced in a recent work [2]. Here we consider, more generally, affine Grassmann codes of a given level. We explicitly determine the dual of an affine Grassmann code of any level and compute its minimum distance. Further, we ameliorate the results of [2] concerning the automorphism group of affine Grassmann codes. Finally, we prove that affine Grassmann codes and their duals have the property that they are linear codes generated by their minimum-weight codewords. This provides a clean analogue of a corresponding result for generalized Reed-Muller codes.
Elaborating on ideas of Elkies, we show how recursive equations for towers of Drinfeld modular curves (X0(Pn))n≥0 for P∈Fq[T] can be read of directly from the modular polynomial ΦP(X,Y) and how this naturally leads to recursions of depth two. Although the modular polynomial ΦT(X,Y) is not known in general, using generators and relations given by Schweizer, we find unreduced recursive equations over Fq(T) for the tower (X0(Tn))n≥2 and of a small variation of it (its partial Galois closure). Reducing at various primes, one obtains towers over finite fields, which are optimal, i.e., reach the Drinfeld--Vladut bound, over a quadratic extension of the finite field. We give a proof of the optimality of these towers, which is elementary and does not rely on their modular interpretation except at one point. We employ the modular interpretation to determine the splitting field of certain polynomials, which are analogues of the Deuring polynomial. For these towers, the particular case of reduction at the prime T−1 corresponds to towers introduced by Elkies and Garcia--Stichtenoth.
We consider a new class of linear codes, called affine Grassmann codes. These can be viewed as a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. We determine the length, dimension, and the minimum distance of any affine Grassmann code. Moreover, we show that affine Grassmann codes have a large automorphism group and determine the number of minimum weight codewords.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.