## On Counting $t$-Cliques Mod 2

#### Webpage for a paper by Oded Goldreich

#### Abstract

For a constant integer $t$, we consider the problem of
counting the number of $t$-cliques *mod 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.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.