Applying discriminant chambers to structured polynomials

One way to prove the algorithmic hardness of a function is to consider its circuit complexity: the minimal size of a circuit computing the function. Recent work in circuit complexity has revealed that it is enough to restrict to depth-4 circuits, inspiring the study of certain structured polynomials called sum-of-products-of-sparse (SPS) polynomials. In particular, showing sufficiently good upper bounds for the number of real roots of SPS polynomials would imply the hardness of the permanent. If f and g are univariate polynomials with real coefficients and t terms, then does fg-1 have a number of real roots that grows at most linearly in t? We consider the first non-trivial approach towards such a bound via A-discriminants, leading to interesting questions involving sparse polynomial systems.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.