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.
