Stasys Jukna

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

Stasys Jukna

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