Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with clique covering number:
TR04-005 | 19th January 2004
Stasys Jukna

On Graph Complexity

Revisions: 1 , Comments: 1

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 ... more >>>

TR05-021 | 14th February 2005
Stasys Jukna

Disproving the single level conjecture

Revisions: 2 , Comments: 1

We consider the minimal number of AND and OR gates in monotone
circuits for quadratic boolean functions, i.e. disjunctions of
length-$2$ monomials. The single level conjecture claims that
monotone single level circuits, i.e. circuits which have only one
level of AND gates, for quadratic functions ... more >>>

ISSN 1433-8092 | Imprint