Theory Seminar

Polynomial Identity Testing for Read Once Polynomials

Daniel MinahanUniversity of Michigan

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.

Sponsored by