Polynomial Identity Testing: Derandomization Results and Applications to Algebraic Computation

Abstract

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. More- over, 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 commu- tative 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.