# IP for Counting Triangles in Graphs#

A function $$f_{A}$$ mapping $$\{0,1\}^{\log n} \times\{0,1\}^{\log n}$$ to $$\{0,1\}$$: Define $$f_{A}(x, y)$$ so that it interprets $$x$$ and $$y$$ as the binary representations of some integers $$i$$ and $$j$$ between 1 and $$n$$, and outputs $$A_{i, j}$$.

Then the number of triangles, $$\Delta$$, in $$G$$ can be written:

$\Delta=\frac{1}{6} \sum_{x, y, z \in\{0,1\}^{\log n}} f_{A}(x, y) \cdot f_{A}(y, z) \cdot f_{A}(x, z) .$

$$\widetilde{f}_{A}$$ is the multilinear extension of $$f_{A}$$ over $$\mathbb{F}$$

To see that this equality is true, observe that the term for $$x, y, z$$ in the above sum is 1 if edges $$(x, y),(y, z)$$, and $$(x, z)$$ all appear in $$G$$, and is 0 otherwise. The factor $$1 / 6$$ comes in because the sum over ordered node triples $$(i, j, k)$$ counts each triangle 6 times, once for each permutation of $$i, j$$, and $$k$$.

$g(X, Y, Z)=\widetilde{f}_{A}(X, Y) \cdot \widetilde{f}_{A}(Y, Z) \cdot \widetilde{f}_{A}(X, Z)$
$6 \Delta=\sum_{x, y, z \in\{0,1\}\}^{\log n}} g(x, y, z)$

So applying the sum-check protocol to $$g$$ yields an IP computing $$6 \Delta$$.