We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}
\item{\em A worst-case to average-case reduction}:
We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For any constant $t$, the reduction runs in ${\widetilde O}(n^2)$-time,
and yields a correct answer (w.h.p.) even when the ``average-case solver'' only succeeds with probability $1/\poly(\log n)$.

\item{\em A direct interactive proof system}:
We present a direct and simple interactive proof system for counting $t$-cliques in $n$-vertex graphs. The proof system uses $t-2$ rounds, the verifier runs in ${\widetilde O}(t^2n^2)$-time, and the prover can be implemented in ${\widetilde O}(t^{O(1)}\cdot n^2)$-time when given oracle access to counting $(t-1)$-cliques in ${\widetilde O}(t^{O(1)}\cdot n)$-vertex graphs. This result extends also to varying $t=t(n)$, yielding alternative interactive proof systems for sets in $\#\cal P$.
\end{enumerate}
The results are both obtained by considering weighted versions of the $t$-clique problem, where weights are assigned to vertices and/or to edges, and the weight of cliques is defined as the product of the corresponding weights.
These weighted problems are shown to be easily reducible to the unweighted problem.

fixing a typo in the definitions of sample-aided reductions

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}
\item{\em A worst-case to average-case reduction}:
We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For any constant $t$, the reduction runs in ${\widetilde O}(n^2)$-time,
and yields a correct answer (w.h.p.) even when the ``average-case solver'' only succeeds with probability $1/\poly(\log n)$.

\item{\em A direct interactive proof system}:
We present a direct and simple interactive proof system for counting $t$-cliques in $n$-vertex graphs. The proof system uses $t-2$ rounds, the verifier runs in ${\widetilde O}(t^2n^2)$-time, and the prover can be implemented in ${\widetilde O}(t^{O(1)}\cdot n^2)$-time when given oracle access to counting $(t-1)$-cliques in ${\widetilde O}(t^{O(1)}\cdot n)$-vertex graphs. This result extends also to varying $t=t(n)$, yielding alternative interactive proof systems for sets in $\#\cal P$.
\end{enumerate}
The results are both obtained by considering weighted versions of the $t$-clique problem, where weights are assigned to vertices and/or to edges, and the weight of cliques is defined as the product of the corresponding weights.
These weighted problems are shown to be easily reducible to the unweighted problem.

Added three appendices (A.2-A.4); see details in Sec 1.5.

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}
\item{\em A worst-case to average-case reduction}:
We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For any constant $t$, the reduction runs in ${\widetilde O}(n^2)$-time,
and yields a correct answer (w.h.p.) even when the ``average-case solver'' only succeeds with probability $1/\poly(\log n)$.

\item{\em A direct interactive proof system}:
We present a direct and simple interactive proof system for counting $t$-cliques in $n$-vertex graphs. The proof system uses $t-2$ rounds, the verifier runs in ${\widetilde O}(t^2n^2)$-time, and the prover can be implemented in ${\widetilde O}(t^{O(1)}\cdot n^2)$-time when given oracle access to counting $(t-1)$-cliques in ${\widetilde O}(t^{O(1)}\cdot n)$-vertex graphs. This result extends also to varying $t=t(n)$, yielding alternative interactive proof systems for sets in $\#\cal P$.
\end{enumerate}
The results are both obtained by considering weighted versions of the $t$-clique problem, where weights are assigned to vertices and/or to edges, and the weight of cliques is defined as the product of the corresponding weights.
These weighted problems are shown to be easily reducible to the unweighted problem.