### Revision(s):

__
Revision #3 to TR20-104 | 17th July 2020 01:43
__
#### On Counting $t$-Cliques Mod 2

**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

**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

**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

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