Search

In this work, we study quantum error-correcting codes obtained by using Steane-enlargement. We apply this technique to certain codes defined from Cartesian products previously considered by Galindo et al. (IEEE Trans Inf Theory 64(4):2444–2459, 2018. 10.1109/TIT.2017.2755682). We give bounds on the dimension increase obtained via enlargement, and additionally give an algorithm to compute the true increase. A number of examples of codes are provided, and their parameters are compared to relevant codes in the literature, which shows that the parameters of the enlarged codes are advantageous. Furthermore, comparison with the Gilbert–Varshamov bound for stabilizer quantum codes shows that several of the enlarged codes match or exceed the parameters promised by the bound. [ABSTRACT FROM AUTHOR]

Using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve over a finite field, we construct sequences with improved high nonlinear complexity. In particular we improve the bound obtained in Niederreiter and Xing (IEEE Trans Inf Theory 60(10):6696–6701, 2014, Theorem 3) considerably and the bound in Niederreiter and Xing (2014, Theorem 4) for some parameters. [ABSTRACT FROM AUTHOR]

LCD codes are linear codes with important cryptographic applications. Recently, a method has been presented to transform any linear code into an LCD code with the same parameters when it is supported on a finite field with cardinality larger than 3. Hence, the study of LCD codes is mainly open for binary and ternary fields. Subfield subcodes of $J$ -affine variety codes are a generalization of BCH codes which have been successfully used for constructing good quantum codes. We describe binary and ternary LCD codes constructed as subfield subcodes of $J$ -affine variety codes and provide some new and good LCD codes coming from this construction. [ABSTRACT FROM AUTHOR]

Two new constructions of linear code pairs C2 \subset C1 are given for which the codimension and the relative minimum distances M1(C1,C2) and M1(C\vphantom {Rj2}^\perp,C1^\perp) are good. By this, we mean that for any two out of the three parameters the third parameter of the constructed code pair is large. Such pairs of nested codes are indispensable for the determination of good linear ramp secret sharing schemes. They can also be used to ensure reliable communication over asymmetric quantum channels. The new constructions result from carefully applying the Feng–Rao bounds to a family of codes defined from multivariate polynomials and Cartesian product point sets. [ABSTRACT FROM AUTHOR]

We consider multivariate polynomials and investigate how many zeros of multiplicity at least r they can have over a Cartesian product of finite subsets of a field. Here r is any prescribed positive integer and the definition of multiplicity that we use is the one related to Hasse derivatives. As a generalization of material in Augot and Stepanov (2009) and Dvir et al. (2009) a general version of the Schwartz–Zippel was presented in Geil and Thomsen (2013) which from the leading monomial – with respect to a lexicographic ordering – estimates the sum of zeros when counted with multiplicity. The corresponding corollary on the number of zeros of multiplicity at least r is in general not sharp and therefore in Geil and Thomsen (2013) a recursively defined function D was introduced using which one can derive improved information. The recursive function being rather complicated, the only known closed formula consequences of it are for the case of two variables (Geil and Thomsen, 2013). In the present paper we derive closed formula consequences for arbitrary many variables, but for the powers in the leading monomial being not too large. Our bound can be viewed as a generalization of the footprint bound (Høholdt, 1998; Geil and Høholdt, 2000)—the classical footprint bound taking not multiplicity into account. [ABSTRACT FROM AUTHOR]

Kopparty and Wang studied in [3] the relation between the roots of a univariate polynomial over F q and the zero–nonzero pattern of its coefficients. We generalize their results to polynomials in more variables. [ABSTRACT FROM AUTHOR]

Salazar, Dunn and Graham in [16] presented an improved Feng-Rao bound for the minimum distance of dual codes. In this work we take the improvement a step further. Both the original bound by Salazar et al., as well as our improvement are lifted so that they deal with generalized Hamming weights. We also demonstrate the advantage of working with one-way well-behaving pairs rather than weakly well-behaving or well-behaving pairs. [ABSTRACT FROM AUTHOR]

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. [ABSTRACT FROM AUTHOR]

Abstract: We show that the Feng–Rao bound for dual codes and a similar bound by Andersen and Geil (2008) [1] for primary codes are consequences of each other. This implies that the Feng–Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique applies to any linear code for which information on well-behaving pairs is available. Consequently we are able to decode efficiently a large class of codes for which no non-trivial decoding algorithm was previously known. Among those are important families of multivariate polynomial codes. Matsumoto and Miura (2000) [30] (see also Beelen and Høholdt, 2008 [3]) derived from the Feng–Rao bound a bound for primary one-point algebraic geometric codes and showed how to decode up to what is guaranteed by their bound. The exposition in Matsumoto and Miura (2000) [30] requires the use of differentials which was not needed in Andersen and Geil (2008) [1]. Nevertheless we demonstrate a very strong connection between Matsumoto and Miuraʼs bound and Andersen and Geilʼs bound when applied to primary one-point algebraic geometric codes. [Copyright &y& Elsevier]

Abstract: We present a new bound on the number of -rational places in an algebraic function field. It uses information about the generators of the Weierstrass semigroup related to a rational place. As we demonstrate, the bound has implications to the theory of towers of function fields. [Copyright &y& Elsevier]

Abstract: The celebrated Feng–Rao bound estimates the minimum distance of codes defined by means of their parity check matrices. From the Feng–Rao bound it is clear how to improve a large family of codes by leaving out certain rows in their parity check matrices. In this paper we derive a simple lower bound on the minimum distance of codes defined by means of their generator matrices. From our bound it is clear how to improve a large family of codes by adding certain rows to their generator matrices. The new bound is very much related to the Feng–Rao bound as well as to Shibuya and Sakaniwa''s bound in [T. Shibuya, K. Sakaniwa, A dual of well-behaving type designed minimum distance, IEICE Trans. Fund. E84-A (2001) 647–652]. Our bound is easily extended to deal with any generalized Hamming weights. We interpret our methods into the setting of order domain theory. In this way we fill in an obvious gap in the theory of order domains. [Copyright &y& Elsevier]

The main results of this paper are derived by using only simple Gro¨bner basis techniques. We present a new construction of evaluation codes from Miura–Kamiya curves Cab. We estimate the minimum distance of the codes and estimate the minimum distance of a class of related one-point geometric Goppa codes. With respect to these estimates the new codes perform at least as well as the related geometric Goppa codes. In particular we consider codes from norm–trace curves. We show that our estimates give actually the true minimum distance of these codes. The new codes from norm–trace curves perform rather well. In many cases much better than the corresponding geometric Goppa codes. It turns out that an alternative description of the new codes from norm–trace curves can be made by using Høholdt et al.'s in: V.S. Pless, W.C. Huffman (Eds.), Handbook of Coding Theory, Vol. 1, Elsevier, Amsterdam, 1998, pp. 871–961 (Chapter 10) construction of improved dual codes. [Copyright &y& Elsevier]

The notion of an order domain is generalized. The behaviour of an order domain by taking a subalgebra, the extension of scalars, and the tensor product is studied. The relation of an order domain with valuation theory, Gro¨bner algebras, and graded structures is given. The theory of Gro¨bner bases for order domains is developed and used to show that the factor ring theorem and its converse, the presentation theorem, hold. The dimension of an order domain is related to the rank of its value semigroup. [Copyright &y& Elsevier]

Presents information on a study which estimated the minimum distance and generalized Hamming weights for a class of error-correcting codes using a generalization of Bezout's theorem. Duals of evaluation codes; Estimation of the number of common zeros; Weight hierarchies for the codes; Conclusions.

Nested code pairs play a crucial role in the construction of ramp secret sharing schemes [15] and in the CSS construction of quantum codes [14]. The important parameters are (1) the codimension, (2) the relative minimum distance of the codes, and (3) the relative minimum distance of the dual set of codes. Given values for two of them, one aims at finding a set of nested codes having parameters with these values and with the remaining parameter being as large as possible. In this work we study nested codes from the Hermitian curve. For not too small codimension, we present improved constructions and provide closed formula estimates on their performance. For small codimension we show how to choose pairs of one-point algebraic geometric codes in such a way that one of the relative minimum distances is larger than the corresponding non-relative minimum distance. [ABSTRACT FROM AUTHOR]

We generalize the unique decoding algorithm for one-point AG codes over the Miura–Kamiya C a b curves proposed by Lee et al. (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng–Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010) . It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals ( Beelen and Brander, 2010; Guruswami and Sudan, 1999 ) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs. [ABSTRACT FROM AUTHOR]

We generalize the list decoding algorithm for Hermitian codes proposed by Lee and OʼSullivan (2009) based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander (2010). Our generalization enables us to apply the fast algorithm to compute a Gröbner basis of a module proposed by Lee and OʼSullivan (2009), which was not possible in another generalization by Lax (2012). [ABSTRACT FROM AUTHOR]