  We address complexity issues for linear differential equations in
characteristic $p>0$: resolution and computation of the $p$-curvature. For
these tasks, our main focus is on algorithms whose complexity behaves well with
respect to $p$. We prove bounds linear in $p$ on the degree of polynomial
solutions and propose algorithms for testing the existence of polynomial
solutions in sublinear time $\tilde{O}(p^{1/2})$, and for determining a whole
basis of the solution space in quasi-linear time $\tilde{O}(p)$; the
$\tilde{O}$ notation indicates that we hide logarithmic factors. We show that
for equations of arbitrary order, the $p$-curvature can be computed in
subquadratic time $\tilde{O}(p^{1.79})$, and that this can be improved to
$O(\log(p))$ for first order equations and to $\tilde{O}(p)$ for classes of
second order equations.

Symbolic Computation