<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Rafael Mendes de Oliveira will present his research seminar/general exam on Wednesday <br>April 30 at 10:15AM in Room 402. The members of his committee are: Zeev Dvir, advisor, Mark <br>Braverman, and Sanjeev Arora. Everyone is invited to attend his talk, and those faculty wishing <br>to remain for the oral exam following are welcome to do so. His abstract and reading list <br>follow below.<br><br><hr id="zwchr"><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div>Abstract:</div><div><br></div><div><div>We show that if f(x_1,...,x_n) is a polynomial with s monomials and g(x_1,...,x_n) divides f then g </div><div>has at most \max(s^{O(\log s \log\log s)},d^{O(\log d)}) monomials, where d is a bound on the individual degrees </div><div>of f. This answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial </div><div>bound holds in this case.</div></div><div><br></div><div>This work is joint work with my advisor, Prof. Dvir.</div><div></div><div></div><div><br></div><div>Reading list:</div><div><br></div><div><div>Book: Arora Barak, Computational Complexity - A Modern Approach<br></div><div><br></div><div>Papers:</div><div><br></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Nisan, Noam. "Lower bounds for non-commutative computation." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Proceedings of the twenty-third annual ACM symposium on Theory of computing</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">. ACM, 1991.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Nisan, Noam, and Avi Wigderson. "Hardness vs randomness." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Journal of Computer and System Sciences</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> 49.2 (1994): 149-167.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Klivans, Adam R., and Daniel Spielman. "Randomness efficient identity testing of multivariate polynomials." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Proceedings of the thirty-third annual ACM symposium on Theory of computing</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">. ACM, 2001.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Kayal, Neeraj. "Affine projections of polynomials." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Proceedings of the 44th symposium on Theory of Computing</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">. ACM, 2012.</span></div><div><br></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Dvir, Zeev, Shubhangi Saraf, and Avi Wigderson. "Improved rank bounds for design matrices and a new proof of Kelly's theorem." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">arXiv preprint arXiv:1211.0330</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> (2012).</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Malod, Guillaume, and Natacha Portier. "Characterizing Valiant's algebraic complexity classes." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Journal of complexity</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> 24.1 (2008): 16-38.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Hrubeš, Pavel, Avi Wigderson, and Amir Yehudayoff. "Non-commutative circuits and the sum-of-squares problem." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Journal of the American Mathematical Society</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> 24.3 (2011): 871-898.</span></div><div><br></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Kaltofen, Erich. "Factorization of polynomials given by straight-line programs."</span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Randomness and Computation</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> 5 (1989): 375-412.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Nisan, Noam, and Avi Wigderson. "Lower bounds on arithmetic circuits via partial derivatives." </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Computational Complexity</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"> 6.3 (1996): 217-234.</span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Valiant, Leslie G. </span><i style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">Graph-theoretic arguments in low-level complexity</i><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);">. Springer Berlin Heidelberg, 1977.</span></div></div><div><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; font-size: 13px; line-height: 16px; background-color: rgb(255, 255, 255);"><br></span></div><br></div><br></div></body></html>