[talks] R Mendes de Oliveira generals

Melissa M. Lawson mml at CS.Princeton.EDU
Thu Apr 24 15:14:16 EDT 2014


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. 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20140424/1669e4ca/attachment.htm>


More information about the talks mailing list