Abstract:

Abstract:
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 or less than two $1$'s the circuit can output arbitrary values. We consider several types of boolean circuits (depth-$3$ circuits and boolean formulas) and show that some explicit graphs cannot be represented by small circuits. As a consequence we obtain that an explicit boolean function in $2m$ variables cannot be computed as an OR of fewer than $2^{\Omega(m)}$ products of linear forms over $GF(2)$. Lower bounds for this model obtainable by previously known (algebraic) arguments do not exceed $2^{O(\sqrt{m})}$. We conclude with a graph-theoretic problem whose solution would have some intriguing consequences in computational complexity.

Comment #1 to TR04-005 | 31st August 2009 13:40

Journal version

Comment:
Journal version published in: Combinatorics, Probability & Computing 15 (2006) 855-876.