Applying discriminant chambers to structured polynomials
MSRIUP 2017: Solving Systems of Polynomial Equations June 24, 2017  August 06, 2017
Location: SLMath: Baker Board Room
Adair, Mendez, Tchuindjo
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.
Adair, Mendez, Tchuindjo
H.264 Video 
Talk_3.mp4

Download 
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.