Title: Arithmetic complexity of symmetric polynomials
Speaker: Pavel Hrubes, Institute of Mathematics of the Academy of Sciences of the Czech Republic
Date: Wednesday, February 11, 2009 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
The problem of proving superpolynomial lower bounds on sizes of formulas computing an explicit polynomial is one of the important open questions in complexity theory. The same applies to more restricted computational models, such as homogeneous formulas. In particular, it is not known whether homogeneous formulas are more powerful than unrestricted formulas.
I will illustrate this problem on the example of elementary symmetric polynomials, which are natural candidates for a potential separation.
(Joint work with Amir Yehudayoff)