  We consider the problem of estimating the number of triangles in a graph.
This problem has been extensively studied in both theory and practice, but all
existing algorithms read the entire graph. In this work we design a {\em
sublinear-time\/} algorithm for approximating the number of triangles in a
graph, where the algorithm is given query access to the graph. The allowed
queries are degree queries, vertex-pair queries and neighbor queries.
  We show that for any given approximation parameter $0<\epsilon<1$, the
algorithm provides an estimate $\widehat{t}$ such that with high constant
probability, $(1-\epsilon)\cdot t< \widehat{t}<(1+\epsilon)\cdot t$, where $t$
is the number of triangles in the graph $G$. The expected query complexity of
the algorithm is $\!\left(\frac{n}{t^{1/3}} + \min\left\{m,
\frac{m^{3/2}}{t}\right\}\right)\cdot {\rm poly}(\log n, 1/\epsilon)$, where
$n$ is the number of vertices in the graph and $m$ is the number of edges, and
the expected running time is $\!\left(\frac{n}{t^{1/3}} +
\frac{m^{3/2}}{t}\right)\cdot {\rm poly}(\log n, 1/\epsilon)$. We also prove
that $\Omega\!\left(\frac{n}{t^{1/3}} + \min\left\{m,
\frac{m^{3/2}}{t}\right\}\right)$ queries are necessary, thus establishing that
the query complexity of this algorithm is optimal up to polylogarithmic factors
in $n$ (and the dependence on $1/\epsilon$).
