<html><body><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000"><div>Please see corrected Building/Room location</div><hr id="zwchr" data-marker="__DIVIDER__"><div data-marker="__HEADERS__"><br></div><div data-marker="__QUOTED_TEXT__"><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;" data-mce-style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;"><div>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.</div><br><div>The members of his committee are as follows: Nonreaders: <span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">Zeev Dvir (adviser), Gillat Kol, Mark Braverman, and Ran Raz; </span>Readers: Zeev Dvir (adviser) and Gillat Kol</div><br><div>A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below:<br></div><br><div>The polynomial identity testing problem (PIT) is a fundamental problem in Complexity<br>Theory, as it is one of the few problems for which there exists a polynomial time randomized<br>algorithm, but no deterministic sub-exponential time algorithm has been discovered. Moreover,<br>many fundamental algorithmic problems can be reduced to particular instances of the<br>PIT problem, which makes its derandomization even more interesting, as it may yield fast<br>deterministic parallel algorithms for such algorithmic problems. The aim of this thesis is to<br>provide new results and new approaches to solving the PIT problem.<br>In the first part of this thesis (Chapter 3), we focus on the PIT problem in the commutative<br>setting. In the first half of this chapter, we provide new deterministic algorithms for<br>multiliinear circuits of low depth and for regular multilinear formulas. In the second half we<br>provide a new application of PIT to the problem of testing equivalences of two polynomials<br>under shifts of the inputs.<br>In the second part of this thesis (Chapter 4), we focus on structural results for factors<br>of commutative polynomials whose degree in each variable is bounded by a constant. We<br>prove that if such a polynomial can be computed by a low-depth circuit of polynomial size,<br>then its factors can also be computed by low-depth circuits of polynomial size. We hope that<br>such structural results provide additional insights in tackling the PIT problem for bounded<br>depth circuits.<br>In the final part of this thesis (Chapter 5), we introduce the setting of non-commutative<br>computation with inversion gates and study the rational identity testing (RIT) problem.<br>We prove the first deterministic polynomial time algorithm for the RIT problem for general<br>non-commutative formulas. Our proof goes via a reduction to the operator scaling problem,<br>which we also discuss in this chapter, and is an analytic approach to the PIT problem, unlike<br>all previous approaches, which are of a purely algebraic nature.</div></div><br>_______________________________________________<br>talks mailing list<br>talks@lists.cs.princeton.edu<br>To edit subscription settings or remove yourself, use this link:<br>https://lists.cs.princeton.edu/mailman/listinfo/talks<br></div></div></body></html>