Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Monotone Unification Problems
event speaker icon
Pavel Hrubes (Princeton University)
event date icon
Wednesday, 21.03.2012, 12:30
event location icon
Taub 201
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.