Logo

Mathematical Sciences Research Institute

Home » MSRI-UP » Schedules » Applying discriminant chambers to structured polynomials

Applying discriminant chambers to structured polynomials

MSRI-UP 2017: Solving Systems of Polynomial Equations June 24, 2017 - August 06, 2017

August 04, 2017 (10:45 AM PDT - 11:20 AM PDT)
Speaker(s): Amy Adair (Louisiana State University), Alex Mendez (University of Illinois at Urbana-Champaign), Diane Tchuindjo (University of Maryland)
Location: MSRI: Baker Board Room
Video

Adair, Mendez, Tchuindjo

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 No Notes/Supplements Uploaded
Video/Audio Files

Adair, Mendez, Tchuindjo

H.264 Video Talk_3.mp4 1.29 GB video/mp4 rtsp://videos.msri.org/data/000/029/317/original/Talk_3.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

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