We develop efficient methods for deterministic computations with semi-algebraic sets and apply them to the problem of counting points on curves and Abelian varieties over finite fields. For Abelian varieties of dimension g in projective N space overFq, we improve Pila's result and show that the problem can be solved in O((logq) δ ) time where δ is polynomial in g as well as in N. For hyperelliptic curves of genus g overFq we show that the number of rational points on the curve and the number of rational points on its Jacobian can be computed in (logq) O ( g 2 l o g g ) time.