__
TR18-046 | 9th March 2018 00:16
__

#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

**Abstract:**
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.