Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-046 | 9th March 2018 00:16

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


Authors: Oded Goldreich, Guy Rothblum
Publication: 9th March 2018 00:16
Downloads: 158


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

\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$.
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.

ISSN 1433-8092 | Imprint