Counting curves and their projections

DOI10.1007/BF01202042zbMath0990.68642MaRDI QIDQ677992

Marek Karpinski, Igor E. Shparlinski, Joachim von zur Gathen

Publication date: 5 May 1999

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

computational complexitycurve counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational aspects of algebraic curves (14Q05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

\#P-completeness of counting roots of a sparse polynomial, On the number of distinct elliptic curves in some families, Computing zeta functions of large polynomial systems over finite fields, Faster \(p\)-adic feasibility for certain multivariate sparse polynomials, Computing the multilinear factors of lacunary polynomials without heights, Counting reducible and singular bivariate polynomials, Algorithms for modular counting of roots of multivariate polynomials, Quantum algorithms for algebraic problems, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Order of torsion for reduction of linearly independent points for a family of Drinfeld modules, Fast computation of a rational point of a variety over a finite field

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit zero-free regions for Dirichlet L-functions
• Matrix multiplication via arithmetic progressions
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Factoring multivariate polynomials over finite fields
• Fast parallel absolute irreducibility testing
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• A deterministic test for permutation polynomials
• Sparse complex polynomials and polynomial reducibility
• There are infinitely many Carmichael numbers
• Tests for permutation functions
• Weil bounds for singular curves
• Computing Frobenius maps and factoring polynomials
• Approximate formulas for some functions of prime numbers
• Tests for Permutation Polynomials
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Factorization of Multivariate Polynomials Over Finite Fields
• Monte-Carlo approximation algorithms for enumeration problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Searching for Primitive Roots in Finite Fields
• Approximating the Number of Zeroes of a GF[2 Polynomial]
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• On Exponential Sums in Finite Fields
• Exponential sums and rational points on complete intersections