ECCC-Report TR18-046https://eccc.weizmann.ac.il/report/2018/046Comments and Revisions published for TR18-046en-usTue, 07 Aug 2018 11:57:34 +0300
Revision 2
| Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2018/046#revision2We 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.
Tue, 07 Aug 2018 11:57:34 +0300https://eccc.weizmann.ac.il/report/2018/046#revision2
Revision 1
| Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2018/046#revision1We 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.
Sun, 01 Apr 2018 16:37:30 +0300https://eccc.weizmann.ac.il/report/2018/046#revision1
Paper TR18-046
| Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2018/046We 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.
Fri, 09 Mar 2018 00:16:39 +0200https://eccc.weizmann.ac.il/report/2018/046