4 papers
On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
Piotr Bacik, Joris Nieuwveld, Joël Ouaknine +3
We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers…
Computing Picard Schemes
Hyuk Jun Kweon, Madhavan Venkatesh
We present an algorithm to compute the torsion component of the Picard scheme of a smooth projective variety over a field . Specifically, we describe $\ma…
Counting points on surfaces in polynomial time
Nitin Saxena, Madhavan Venkatesh
We present a randomised algorithm to compute the local zeta function of a fixed smooth, projective surface over , at any large prime of good reduction. The runtime…
Complexity of counting points on curves and the factor 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-…