Counting curves and their projections

Joachim von Zur Gathen*, Marek Karpinski, Igor Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

8 Citations (Scopus)

Abstract

Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. Classical questions on estimating the size of the image of a univariate polynomial are special cases. For sparse polynomials, the counting problem is #P-complete via probabilistic Turing reductions, under an unproven number-theoretical assumption.

Original languageEnglish
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC '93
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages805-812
Number of pages8
ISBN (Print)0897915917
Publication statusPublished - 1993
Externally publishedYes
EventProceedings of the 25th Annual ACM Symposium on the Theory of Computing - San Diego, CA, USA
Duration: 16 May 199318 May 1993

Other

OtherProceedings of the 25th Annual ACM Symposium on the Theory of Computing
CitySan Diego, CA, USA
Period16/05/9318/05/93

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

Cite this