Counting $t$-cliques: Worst-case to average-case reductions
and Direct interactive proof systems
Webpage for a paper by Oded Goldreich and Guy Rothblum
Abstract
We present two main results regarding
the complexity of counting the number of $t$-cliques in a graph.
- 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)$.
- 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.
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.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.