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 Urbana-Champaign), 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 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.
- Supplements
-
--
|
|