COUNTING CURVES AND THEIR PROJECTIONS

Authors
GATHEN JV KARPINSKI M SHPARLINSKI I
Citation
Jv. Gathen et al., COUNTING CURVES AND THEIR PROJECTIONS, Computational complexity, 6(1), 1996, pp. 64-99
Citations number
46
Categorie Soggetti
Mathematics, General","Computer Sciences",Mathematics,"Computer Science Theory & Methods
Journal title
Computational complexity → ACNP
ISSN journal
10163328
Volume
6
Issue
1
Year of publication
1996
Pages
64 - 99
Database
ISI
SICI code
1016-3328(1996)6:1<64:CCATP>2.0.ZU;2-M
Abstract
Some deterministic and probabilistic methods are presented for countin g and estimating the number of points on curves over finite fields, an d 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-comDlete via p robabilistic parsimonious Turing reductions.