School of Technology and Computer Science Seminars

Lowerbound against homogeneous multilinear formulas

by Prerorna Chaterjee (STCS, TIFR)

Friday, September 13, 2019 from to (Asia/Kolkata)
at TIFR ( A-201 STCS Seminar Room )
Description
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.