[talks] Correction: Building/Rm: 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

[Nicki Gotsis]

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 at lists.cs.princeton.edu 
To edit subscription settings or remove yourself, use this link: 
https://lists.cs.princeton.edu/mailman/listinfo/talks 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20170718/963eedeb/attachment.html>