On Counting $t$-Cliques Mod 2

Webpage for a paper by Oded Goldreich


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.