ECCC-Report TR20-104https://eccc.weizmann.ac.il/report/2020/104Comments and Revisions published for TR20-104en-usFri, 17 Jul 2020 01:43:51 +0300
Revision 3
| On Counting $t$-Cliques Mod 2 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/104#revision3For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The reduction runs in linear time when graphs are presented by their adjacency matrices, and average-case is with respect to the uniform distribution over graphs with a given number of vertices.
Correction (July 16th, 2020):
It turns out that the foregoing results were previously obtained by Boix-Adsera, Brennan, and Bresler (FOCS'19), using a slightly more complex worst-case to average-case reduction.
Fri, 17 Jul 2020 01:43:51 +0300https://eccc.weizmann.ac.il/report/2020/104#revision3
Revision 2
| On Counting $t$-Cliques Mod 2 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/104#revision2For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The reduction runs in linear time when graphs are presented by their adjacency matrices, and average-case is with respect to the uniform distribution over graphs with a given number of vertices.
Mon, 13 Jul 2020 20:26:09 +0300https://eccc.weizmann.ac.il/report/2020/104#revision2
Revision 1
| On Counting $t$-Cliques Mod 2 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/104#revision1For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The reduction runs in linear time when graphs are presented by their adjacency matrices, and average-case is with respect to the uniform distribution over graphs with a given number of vertices.
Sun, 12 Jul 2020 20:47:05 +0300https://eccc.weizmann.ac.il/report/2020/104#revision1
Paper TR20-104
| On Counting $t$-Cliques Mod 2 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/104For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The reduction runs in linear time when graphs are presented by their adjacency matrices, and average-case is with respect to the uniform distribution over graphs with a given number of vertices.
Sun, 12 Jul 2020 18:14:08 +0300https://eccc.weizmann.ac.il/report/2020/104