Rafael Mendes de Oliveira will present his research seminar/general exam on Wednesday April 30 at 10:15AM in Room 402. The members of his committee are: Zeev Dvir, advisor, Mark Braverman, and Sanjeev Arora. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- Abstract: 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 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 of f. This answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds in this case. This work is joint work with my advisor, Prof. Dvir. Reading list: Book: Arora Barak, Computational Complexity - A Modern Approach Papers: Nisan, Noam. "Lower bounds for non-commutative computation." Proceedings of the twenty-third annual ACM symposium on Theory of computing . ACM, 1991. Nisan, Noam, and Avi Wigderson. "Hardness vs randomness." Journal of Computer and System Sciences 49.2 (1994): 149-167. Klivans, Adam R., and Daniel Spielman. "Randomness efficient identity testing of multivariate polynomials." Proceedings of the thirty-third annual ACM symposium on Theory of computing . ACM, 2001. Kayal, Neeraj. "Affine projections of polynomials." Proceedings of the 44th symposium on Theory of Computing . ACM, 2012. Dvir, Zeev, Shubhangi Saraf, and Avi Wigderson. "Improved rank bounds for design matrices and a new proof of Kelly's theorem." arXiv preprint arXiv:1211.0330 (2012). Malod, Guillaume, and Natacha Portier. "Characterizing Valiant's algebraic complexity classes." Journal of complexity 24.1 (2008): 16-38. Hrubeš, Pavel, Avi Wigderson, and Amir Yehudayoff. "Non-commutative circuits and the sum-of-squares problem." Journal of the American Mathematical Society 24.3 (2011): 871-898. Kaltofen, Erich. "Factorization of polynomials given by straight-line programs." Randomness and Computation 5 (1989): 375-412. Nisan, Noam, and Avi Wigderson. "Lower bounds on arithmetic circuits via partial derivatives." Computational Complexity 6.3 (1996): 217-234. Valiant, Leslie G. Graph-theoretic arguments in low-level complexity . Springer Berlin Heidelberg, 1977.