  We study the problem of counting the number of {\em isomorphic} copies of a
given {\em template} graph, say $H$, in the input {\em base} graph, say $G$. In
general, it is believed that polynomial time algorithms that solve this problem
exactly are unlikely to exist. So, a lot of work has gone into designing
efficient {\em approximation schemes}, especially, when $H$ is a perfect
matching.
  In this work, we present efficient approximation schemes to count
$k$-Cliques, $k$-Independent sets and $k$-Clique covers in random graphs. We
present {\em fully polynomial time randomized approximation schemes} (fpras) to
count $k$-Cliques and $k$-Independent sets in a random graph on $n$ vertices
when $k$ is at most $(1+o(1))\log n$, and $k$-Clique covers when $k$ is a
constant. [Grimmett and McDiarmid, 1975] present a simple greedy algorithm that
{\em detects} a clique (independent set) of size $(1+o(1))\log_2 n$ in $G\in
\mathcal{G}(n,\frac{1}{2})$ with high probability. No algorithm is known to
detect a clique or an independent set of larger size with non-vanishing
probability. Furthermore, [Coja-Oghlan and Efthymiou, 2011] present some
evidence that one cannot hope to easily improve a similar, almost 40 years old
bound for sparse random graphs. Therefore, our results are unlikely to be
easily improved.
  We use a novel approach to obtain a recurrence corresponding to the variance
of each estimator. Then we upper bound the variance using the corresponding
recurrence. This leads us to obtain a polynomial upper bound on the critical
ratio. As an aside, we also obtain an alternate derivation of the closed form
expression for the $k$-th moment of a binomial random variable using our
techniques. The previous derivation [Knoblauch (2008)] was based on the moment
generating function of a binomial random variable.
