Rafael Oliveira will present his Pre FPO, "Polynomial identity testing: derandomization results and applications" on Monday, May 8, 2017 at 2pm in CS 302.

The members of his committee are: Zeev Dvir (adviser/reader), Gillat Kol (reader), Mark Braverman (examiner), and Ran Raz (examiner)

Everyone is invited to attend his talk.  The talk title and abstract follow below:

Title:
Polynomial identity testing: derandomization results and applications

Abstract:
The purpose of algebraic complexity theory is to provide a framework for understanding the powers and limitations of computation when the resources used and the computations performed are of an algebraic nature. Many important computational problems in computer science, mathematics and physics can be cast in an algebraic way, and understanding the computational complexity of the algebraic structures arising from such formulations is one of the chief goals of the theory.

In this thesis, we study two fundamental problems in algebraic complexity theory: the derandomization of the polynomial identity testing problem (and of its non-commutative variant) and the parallel complexity of factoring polynomials. We will show connections between these two problems and how these problems can be used to solve computational questions in invariant theory, non-commutative algebra, quantum physics and combinatorics.