Skip navigation
Please use this identifier to cite or link to this item:
Title: Polynomial Identity Testing: Derandomization Results and Applications to Algebraic Computation
Authors: Mendes de Oliveira, Rafael
Advisors: Dvir, Zeev
Contributors: Computer Science Department
Subjects: Computer science
Issue Date: 2017
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
MendesdeOliveira_princeton_0181D_12282.pdf1.12 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.