Aug 04, 2017
Friday

10:45 AM  11:20 AM


Applying discriminant chambers to structured polynomials
Amy Adair (Louisiana State University), Alex Mendez (University of Illinois at UrbanaChampaign), Diane Tchuindjo (University of Maryland)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
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 depth4 circuits, inspiring the study of certain structured polynomials called sumofproductsofsparse (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 fg1 have a number of real roots that grows at most linearly in t? We consider the first nontrivial approach towards such a bound via Adiscriminants, leading to interesting questions involving sparse polynomial systems.
 Supplements



