  In this paper we introduce a general framework for casting fully dynamic
transitive closure into the problem of reevaluating polynomials over matrices.
With this technique, we improve the best known bounds for fully dynamic
transitive closure. In particular, we devise a deterministic algorithm for
general directed graphs that achieves $O(n^2)$ amortized time for updates,
while preserving unit worst-case cost for queries. In case of deletions only,
our algorithm performs updates faster in O(n) amortized time.
  Our matrix-based approach yields an algorithm for directed acyclic graphs
that breaks through the $O(n^2)$ barrier on the single-operation complexity of
fully dynamic transitive closure. We can answer queries in $O(n^\epsilon)$ time
and perform updates in $O(n^{\omega(1,\epsilon,1)-\epsilon}+n^{1+\epsilon})$
time, for any $\epsilon\in[0,1]$, where $\omega(1,\epsilon,1)$ is the exponent
of the multiplication of an $n\times n^{\epsilon}$ matrix by an
$n^{\epsilon}\times n$ matrix. The current best bounds on
$\omega(1,\epsilon,1)$ imply an $O(n^{0.58})$ query time and an $O(n^{1.58})$
update time. Our subquadratic algorithm is randomized, and has one-side error.
