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 #3 to TR20-104 | 17th July 2020 01:43

On Counting $t$-Cliques Mod 2

RSS-Feed




Revision #3
Authors: Oded Goldreich
Accepted on: 17th July 2020 01:43
Downloads: 61
Keywords: 


Abstract:

For 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.



Changes to previous version:

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.


Revision #2 to TR20-104 | 13th July 2020 20:26

On Counting $t$-Cliques Mod 2





Revision #2
Authors: Oded Goldreich
Accepted on: 13th July 2020 20:26
Downloads: 72
Keywords: 


Abstract:

For 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.



Changes to previous version:

Adding references to two related works (see [WWWY,AFW20]).


Revision #1 to TR20-104 | 12th July 2020 20:47

On Counting $t$-Cliques Mod 2





Revision #1
Authors: Oded Goldreich
Accepted on: 12th July 2020 20:47
Downloads: 137
Keywords: 


Abstract:

For 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.



Changes to previous version:

The combinatorial conjecture, which was proved only for the cases of $t=3$ and $t=4$, was actually proved as a very special case by Kolaitis and Kopparty (JACM 2013). The current revision is corrected accordingly.


Paper:

TR20-104 | 12th July 2020 18:13

On Counting $t$-Cliques Mod 2





TR20-104
Authors: Oded Goldreich
Publication: 12th July 2020 18:14
Downloads: 143
Keywords: 


Abstract:

For 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.



ISSN 1433-8092 | Imprint