Rafael Mendes de Oliveira will present his FPO, "Polynomial Identity Testing: Derandomization Results and Applications to Algebraic Computation" on Friday, July 21, 2017 at 1pm in Friend Center 401.
The members of his committee are as follows: Nonreaders: Zeev Dvir (adviser), Gillat Kol, Mark Braverman, and Ran Raz; Readers: Zeev Dvir (adviser) and Gillat Kol
A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below:
The polynomial identity testing problem (PIT) is a fundamental problem in Complexity
Theory, as it is one of the few problems for which there exists a polynomial time randomized
algorithm, but no deterministic sub-exponential time algorithm has been discovered. Moreover,
many fundamental algorithmic problems can be reduced to particular instances of the
PIT problem, which makes its derandomization even more interesting, as it may yield fast
deterministic parallel algorithms for such algorithmic problems. The aim of this thesis is to
provide new results and new approaches to solving the PIT problem.
In the first part of this thesis (Chapter 3), we focus on the PIT problem in the commutative
setting. In the first half of this chapter, we provide new deterministic algorithms for
multiliinear circuits of low depth and for regular multilinear formulas. In the second half we
provide a new application of PIT to the problem of testing equivalences of two polynomials
under shifts of the inputs.
In the second part of this thesis (Chapter 4), we focus on structural results for factors
of commutative polynomials whose degree in each variable is bounded by a constant. We
prove that if such a polynomial can be computed by a low-depth circuit of polynomial size,
then its factors can also be computed by low-depth circuits of polynomial size. We hope that
such structural results provide additional insights in tackling the PIT problem for bounded
depth circuits.
In the final part of this thesis (Chapter 5), we introduce the setting of non-commutative
computation with inversion gates and study the rational identity testing (RIT) problem.
We prove the first deterministic polynomial time algorithm for the RIT problem for general
non-commutative formulas. Our proof goes via a reduction to the operator scaling problem,
which we also discuss in this chapter, and is an analytic approach to the PIT problem, unlike
all previous approaches, which are of a purely algebraic nature.
