International Mathematics Research Papers · 2006 · 50 citations · 25 references
ComputingComputer ScienceAlgorithmsComputational GeometryTheory Of ComputationArithmetic GeometryComputational ComplexityComputational Number TheoryComputing Zeta FunctionsFinite Field ArithmeticNewton PolytopesP-adic AlgorithmsP-adic CohomologyP-adic FieldsP-adic Zeta FunctionsSpace Complexity Analysis
We present a p-adic algorithm to compute the zeta function of a nondegenerate curve over a finite field using Monsky-Washnitzer cohomology. The paper vastly generalizes previous work since in practice all known cases, for example, hyperelliptic, superelliptic, and Cab curves, can be transformed to fit the nondegenerate case. For curves with a fixed Newton polytope, the property of being nondegenerate is generic, so that the algorithm works for almost all curves with given Newton polytope. For a genus g curve over Fpn, the expected running time is Õ(n3g6 + n2g6.5), whereas the space complexity amounts to Õ(n3g4), assuming p is fixed.
25
THE GEOMETRY OF TORIC VARIETIES
V. I. Danilov · Russian Mathematical Surveys · 1978 · 925 citations
Sharp effective Nullstellensatz
Janós Kollár · Journal of the American Mathematical Society · 1988 · 234 citations · Full text