A monotone Boolean circuit is a restriction of a Boolean circuit
allowing for the use of disjunctions, conjunctions, the Boolean
constants, and the input variables. A monotone Boolean circuit is
multilinear if for any AND gate the two input functions have no
variable in common. We ... more >>>

We study the power of negation in the Boolean and algebraic settings and show the following results.

* We construct a family of polynomials $P_n$ in $n$ variables, all of whose monomials have positive coefficients, such that $P_n$ can be computed by a depth three circuit of polynomial size ... more >>>