ECCC-Report TR04-005https://eccc.weizmann.ac.il/report/2004/005Comments and Revisions published for TR04-005en-usMon, 31 Aug 2009 13:40:18 +0300
Comment 1
| Journal version |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/005#comment1Journal version published in: Combinatorics, Probability & Computing 15 (2006) 855-876. Mon, 31 Aug 2009 13:40:18 +0300https://eccc.weizmann.ac.il/report/2004/005#comment1
Revision 1
| |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/005#revision1Mon, 14 Feb 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2004/005#revision1
Paper TR04-005
| On Graph Complexity |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/005 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.
Tue, 20 Jan 2004 08:26:35 +0200https://eccc.weizmann.ac.il/report/2004/005