#P-completeness of counting roots of a sparse polynomial
t is known (from Counting curves and their projections by Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski [1, part 4]) that counting the number of points on a curve where is a sparse polynomial over
is #P-complete under randomized reductions.
We give a simple proof of a stronger result: counting roots of a sparse univariate polynomial over
is #P-complete under deterministic reductions.