Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DEPTH-$3$ CIRCUITS:
Reports tagged with depth-$3$ circuits:
TR04-005 | 19th January 2004
Stasys Jukna

#### On Graph Complexity

A boolean circuit $f(x_1,\ldots,x_n)$ \emph{represents} a graph $G$
on $n$ vertices if for every input vector $a\in\{0,1\}^n$ with
precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$
precisely when $i$ and $j$ are adjacent in $G$; on inputs with more