Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?
Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).
Non-example: it takes $O(\log p)$ time to count (and output) the $\mathrm{mod}\:p$ solutions of $x+y=0$ as there are $p$ solutions.
 A: At least for fixed degree, the answer appears to be 'no' — it seems to be well-established that the number of roots of a univariate polynomial $g(x)$ of degree $d$ modulo a prime $p$ can be determined in $O\left((d+\log p)^{O(1)}\right)$ time, which gives a quasilinear time algorithm for a polynomial $f(x,y)$ by just evaluating $f()$ at each value of $y$ to find $p$ univariate polynomials (which can be done in basically $O(dp)$ time) and count the number of roots for each in turn. This means that for any fixed polynomial, it can be done in $O(p(\log p)^{O(1)})$ time as $p$ increases. I don't know whether you can get time sub-linear in $p$, though I wouldn't be surprised if it was an open question. Note that 'linear in $p$' here is still exponential in the size of the input (giving $p$ in binary) and that's the usual metric for this sort of problem for large $p$, so the usual target here is really something in $p^{o(1)}$.
If we allow for an arbitrary polynomial of degree $\lt p$ then this no longer works, but note that then the input naively has size $\Theta(p^2)$ so we can't even read all the data in less time then that. The one case I can't account for is the case of sparse bivariate polynomials of arbitrarily high degree mod $p$, where it seems from at least a bit of digging like not much is specifically known.
