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.
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.
Please see corrected Building/Room location 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 CS 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. _______________________________________________ talks mailing list talks@lists.cs.princeton.edu To edit subscription settings or remove yourself, use this link: https://lists.cs.princeton.edu/mailman/listinfo/talks
participants (1)
-
Nicki Gotsis