β Scribed by Ming-Deh Huang; Doug Ierardi
No coin nor oath required. For personal study only.
We study the effective Riemann-Roch problem of computing a basis for the linear space (L(D)) associated with a divisor (D) on a plane curve (C) and its applications. Our presentation begins with an extension of Noether's algorithm for this problem to plane curves with singularities. Like the original, this algorithm has a worst-case complexity of (\Omega(n!|D|)), where (n) is the degree of the curve (C).
We next consider representations of divisors based on Chow forms. Using these, we produce a factorization-free polynomial-time algorithm for the effective Riemann-Roch problem, which improves the complexity of Noether's algorithm by an order of magnitude. We also present further improvements which, for curves of bounded degree, yield an algorithm with complexity which is linear in the size of the given divisor. Finally, we consider applications of this problem: to the arithmetic of the Jacobian of a plane curve, to the construction of rational functions on a curve with prescribed zeroes and poles, and to the construction of curves with prescribed intersections.
π SIMILAR VOLUMES
In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint