Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-046 | 7th August 2018 11:57

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

RSS-Feed




Revision #2
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 7th August 2018 11:57
Downloads: 42
Keywords: 


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.



Changes to previous version:

fixing a typo in the definitions of sample-aided reductions


Revision #1 to TR18-046 | 1st April 2018 16:37

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





Revision #1
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 1st April 2018 16:37
Downloads: 114
Keywords: 


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.



Changes to previous version:

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


Paper:

TR18-046 | 9th March 2018 00:16

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





TR18-046
Authors: Oded Goldreich, Guy Rothblum
Publication: 9th March 2018 00:16
Downloads: 350
Keywords: 


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.



ISSN 1433-8092 | Imprint