Search

In this paper, we consider roots of multivariate polynomials over a finite grid. When given information on the leading monomial with respect to a fixed monomial ordering, the footprint bound [Footprints or generalized Bezout's theorem, IEEE Trans. Inform. Theory46(2) (2000) 635–641, On (or in) Dick Blahut's 'footprint', Codes , Curves Signals (1998) 3–9] provides us with an upper bound on the number of roots, and this bound is sharp in that it can always be attained by trivial polynomials being a constant times a product of an appropriate combination of terms consisting of a variable minus a constant. In contrast to the one variable case, there are multivariate polynomials attaining the footprint bound being not of the above form. This even includes irreducible polynomials. The purpose of the paper is to determine a large class of polynomials for which only the mentioned trivial polynomials can attain the bound, implying that to search for other polynomials with the maximal number of roots one must look outside this class. [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]

Asymptotically good sequences of ramp secret sharing schemes were given in [5] by using one-point algebraic geometric codes defined from asymptotically good towers of function fields. Their security is given by the relative generalized Hamming weights of the corresponding codes. In this paper we demonstrate how to obtain refined information on the RGHWs when the codimension of the codes is small. For general codimension, we give an improved estimate for the highest RGHW. [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]

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]