Counting curves and their projections

Joachim Von Zur Gathen*, Marek Karpinski, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)


Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is #P-complete via probabilistic parsimonious Turing reductions.

Original languageEnglish
Pages (from-to)64-99
Number of pages36
JournalComputational Complexity
Issue number1
Publication statusPublished - 1996


Dive into the research topics of 'Counting curves and their projections'. Together they form a unique fingerprint.

Cite this