TITLE: Polynomial Factorization and Algebraic Complexity

ABSTRACT:

In this talk, I will discuss connections between three central problems in algebraic complexity theory: arithmetic circuit lower bounds, derandomization questions in arithmetic computation, and polynomial factorization. These three closely related topics have guided algebraic complexity in the last several decades. I will talk about the interrelations between these problems and also some recent results towards the quest of deterministic multivariate polynomial factorization.

BIO:

Shubhangi Saraf is an associate professor in the computer science and mathematics departments at Rutgers University. Her research interests lie broadly in theoretical computer science with a focus in arithmetic complexity, error correcting codes, and sublinear time algorithms. She received her bachelor’s degree in mathematics from MIT in 2007 and then a Ph.D. degree in computer science from MIT in 2011. Prior to joining the faculty of Rutgers University in 2012, she spent a year as a postdoctoral researcher at the Institute for Advanced Study (IAS). She is a recipient of the Alfred P. Sloan Research Fellowship and the NSF CAREER Award.