Counting curves and their projections

Joachim von Zur Gathen; Marek Karpinski; Igor Shparlinski

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 proceeding › Conference proceeding contribution › peer-review

9 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 language	English
Title of host publication	Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC '93
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Pages	805-812
Number of pages	8
ISBN (Print)	0897915917
Publication status	Published - 1993
Externally published	Yes
Event	Proceedings of the 25th Annual ACM Symposium on the Theory of Computing - San Diego, CA, USA Duration: 16 May 1993 → 18 May 1993

Other

Other	Proceedings of the 25th Annual ACM Symposium on the Theory of Computing
City	San Diego, CA, USA
Period	16/05/93 → 18/05/93

Cite this

@inproceedings{9eccafb53a5b486eb6262a6d19114c31,

title = "Counting curves and their projections",

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.",

author = "\{von Zur Gathen\}, Joachim and Marek Karpinski and Igor Shparlinski",

year = "1993",

language = "English",

isbn = "0897915917",

pages = "805--812",

booktitle = "Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC '93",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

note = "Proceedings of the 25th Annual ACM Symposium on the Theory of Computing ; Conference date: 16-05-1993 Through 18-05-1993",

}

TY - GEN

T1 - Counting curves and their projections

AU - von Zur Gathen, Joachim

AU - Karpinski, Marek

AU - Shparlinski, Igor

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0027148929

M3 - Conference proceeding contribution

AN - SCOPUS:0027148929

SN - 0897915917

SP - 805

EP - 812

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC '93

PB - Association for Computing Machinery (ACM)

CY - New York

T2 - Proceedings of the 25th Annual ACM Symposium on the Theory of Computing

Y2 - 16 May 1993 through 18 May 1993

ER -

Counting curves and their projections

Abstract

Other

Other files and links

Fingerprint

Cite this