דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
פבל רובס (אונ' פרינסטון)
event date icon
יום רביעי, 21.03.2012, 12:30
event location icon
טאוב 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.