Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces

Diptajit Roy, Nitin Saxena, Madhavan Venkatesh

This article concerns the computational complexity of a fundamental problem in number theory: counting points on curves and surfaces over finite fields. There is no subexponential-…