Monotone Unification Problems

Computer Science/Discrete Mathematics Seminar I
Topic:Monotone Unification Problems
Speaker:Pavel Hrubes
Affiliation:University of Calgary
Date:Monday, December 12
Time/Room:11:15am - 12:15pm/S-101

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.