Home /  MsriUp /  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 (Massachusetts Institute of Technology)
Location: SLMath: 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
Troubles with video?

Please report video problems to itsupport@slmath.org.

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