Computer Science/Discrete Mathematics Seminar I

Given two monotone polynomials f,g, their unifier is a pair of monotone polynomials u,v such that f=cu+v and g=u+cv, for some c>0. The problem I will discuss is: can we have monotone polynomials f,g which have a unifier, they can be computed by a small monotone circuit, but every unifier of f,g requires a large monotone circuit? On one hand, the question is related to arithmetic circuit complexity, and on the other, to the complexity of proofs in subsystems of monotone calculus (or the Frege system). The unification problem can be formulated in several different settings: the simplest is the context of the non-negative rank of real matrices. Here, one is required to give quite a strong separation between the real rank and the non-negative rank of a matrix - while more modest separations are not known.