Lowerbound against homogeneous multilinear formulas

Speaker: 

Time: 

Friday, 13 September 2019, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

Abstract: A polynomial is said to be multilinear if the individual degree of every variable is at most one in any monomial; and is said to be homogeneous if every monomial in it has the same degree. Many polynomials of interest (like the determinant or the permanent of a symbolic matrix) are homogeneous multilinear polynomials.  An algebraic formula is a model for computing polynomials and is said to be a homogeneous multilinear one if every gate in it computes a homogeneous multilinear polynomial. Hrubes and Yehudayoff (in their 2011 paper) showed that any polynomial that is computed by a homogeneous multilinear formula has a very special decomposition (called the log-product decomposition) and used it to give a lowerbound against this model. In today's talk, we will see the full proof of this lowerbound.