Tata Institute of Fundamental Research
Lowerbound against homogeneous multilinear formulas
STCS Student Seminar
Speaker:
Prerona Chatterjee
Organiser:
Anamay Tengse
Date:
Friday, 13 Sep 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Prerona Chatterjee |
| Organiser: | Anamay Tengse |
| Date: | Friday, 13 Sep 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.