Theory Seminar
Polynomial Identity Testing for Read Once Polynomials
Daniel MinahanUniversity of Michigan
WHEN:
Friday, October 7, 2016 @ 10:30 am
Add to Google Calendar
Add to Google Calendar
SHARE:
A read once polynomial is a polynomial in many variables which can be expressed in such a way
that each variable appears only once and has a degree of at most one. We are given a read once
polynomial in an arbitrary field and wish to design an algorithm that rapidly determines if the polynomial is
identically zero or not. In particular, we do this in a black box, which means that we can only send inputs to
the polynomial and receive outputs. We would like our algorithm to run in polynomial time.