left-arrowleft-arrowright-arrowleft-arrowAsset 9
'
Loading Events

« All Events

  • This event has passed.

Calculus, Real Fewnomials, and P vs NP

October 30, 2019 @ 4:15 pm - 5:15 pm

We review a beautiful 17th century result by the philosopher Rene Descartes: a univariate real polynomial with t monomial terms has no more than t-1 positive roots. We then see how one can prove a generalization that counts roots of two bivariate polynomials (with few monomial terms), using nothing more than basic calculus. In other words, we’ll see the basics of real fewnomial theory. We’ll then see how this relates to circuit complexity and the famous P vs. NP Problem. In particular, we’ll see how new bounds in real fewnomial theory lead to new separations of complexity classes that answer deep questions in theoretical computer science. Along the way, we’ll see some of the ideas behind tropical geometry.

Details

Date:
October 30, 2019
Time:
4:15 pm - 5:15 pm
Event Category:

Venue

Argue Auditorium, Pomona College
610 N. College Ave.
Claremont, CA 91711 United States
+ Google Map