One-point codes are those algebraic-geometry codes for which the associated divisor is a non-negative multiple of a single point. Evaluation codes were defined in order to give an algebraic generalization of both one-...
详细信息
One-point codes are those algebraic-geometry codes for which the associated divisor is a non-negative multiple of a single point. Evaluation codes were defined in order to give an algebraic generalization of both one-point algebraic-geometry codes and Reed-Muller codes. Given an F-q-algebra A, an order function rho on A and given a surjective F-q-morphism of algebras phi: A -> F-q(n), the ith evaluation code with respect to A, rho, phi is defined as the code C-i = phi(f is an element of A : rho(f) <= i}). In this work it is shown that under a certain hypothesis on the F-q-algebra A, not only any evaluation code is a one-point code, but any sequence of evaluation codes is a sequence of one-point codes. This hypothesis on A is that its field of fractions is a function field over F-q and that A is integrally closed. Moreover, we see that a sequence of algebraic-geometry codes G(i) with associated divisors Gamma(i) is the sequence of evaluation codes associated to some F-q-algebra A, some order function rho and some surjective morphism phi with {f is an element of A : rho(f) <= i} = L(Gamma(i)) if and only if it is a sequence of one-point codes.
Function-field codes provide a general perspective on the construction of algebraic-geometry codes. We briefly review the theory of function-field codes and establish some new results in this theory, including a propa...
详细信息
Function-field codes provide a general perspective on the construction of algebraic-geometry codes. We briefly review the theory of function-field codes and establish some new results in this theory, including a propagation rule. We show how to derive linear codes from function-field codes, thus generalizing a construction of linear codes due to Xing, Niederreiter, and Lam.
In this correspondence, we study disjoint linear codes and give constructions of families of disjoint linear codes based on algebraic function fields. It turns out that, for some parameters, our constructions improve ...
详细信息
In this correspondence, we study disjoint linear codes and give constructions of families of disjoint linear codes based on algebraic function fields. It turns out that, for some parameters, our constructions improve on a result of Johansson and Pasalic.
We introduce a new class of nonlinear algebraic-geometry codes based on evaluation of functions on infinitely near points. Let X be an algebraic variety over the finite field F-q. An infinitely near point of order mu ...
详细信息
We introduce a new class of nonlinear algebraic-geometry codes based on evaluation of functions on infinitely near points. Let X be an algebraic variety over the finite field F-q. An infinitely near point of order mu is a point P on a variety X' obtained by mu iterated blowing-ups starting from X. Given such a point P and a function f on X, we give a definition of f(P) which is nonlinear in f (unless mu = 0). Given a set S of infinitely near points {P-1, . . . , P-n}, we associate to f its set of values (f(P-1), . . . , f(P-n)) in F-q(n). Let V be a k dimensional vector space of functions on X. Evaluation of functions in V at the n points of S gives a map V -> F-q(n), which we view as an (n, q(k), d) code when the map is injective. Here d is the largest integer such that a function in V is uniquely determined by its values on any n - d + 1 points of S. These codes generalize the Reed-Solomon codes, but unlike the R-S codes they can be constructed to have arbitrarily large code length n. The first nontrivial case is where X = A(Fq)(2), affine 2-space, and we study this case in detail.
We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis ...
详细信息
ISBN:
(纸本)9781450355599
We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis (SETH) is false, for every delta > 0 there exists a constant epsilon > 0 such that computing a (1 + epsilon)-approximation to the Bichromatic Closest Pair requires Omega (n(2-delta)) time. In particular, this implies a near-linear query time for Approximate Nearest Neighbor search with polynomial preprocessing time. Our reduction uses the recently introduced Distributed PCP framework, but obtains improved efficiency using algebraicgeometry (AG) codes. Efficient PCPs from AG codes have been constructed in other settings before, but our construction is the first to yield new hardness results.
暂无评论