Seminar Type: Invited Speakers
Title: Non-Commutative Arithmetic Circuits and the Sum of Squares Problem
Start Time: 11/23/2009 - 12:00
End Time: 11/23/2009 - 13:00
Location: ICT 616
Speaker: Pavel Hrubes
Abstract:
The arithmetic circuit is a basic model for computing polynomials over a given field. In a non-commutative polynomial, variables do not multiplicatively commute; one can think of the variables as representing matrices. I will discuss non-commutative arithmetic circuits, which compute non-commutative polynomials. The major open question is to prove a superpolynomial lower bound on the size of a circuit computing an explicit non-commutative polynomial. This question is related to a classical mathematical problem, the so called sum of squares problem. This problem lies on the boundary of algebra and topology, and is interesting from a purely mathematical point of view. I will sketch the connection between non-commutative arithmetic circuits and sum of squares, and proceed to discuss mathematical aspects of the sum of squares problem. (Joint work with Amir Yehudayoff and Avi Wigderson.)
Biography:Pavel Hrubes received his Ph.D. in mathematics in 2007 from the Charles University in Prague. Afterwards he became a postdoctoral fellow at the University of Toronto, and since 2008 he has been a postdoctoral fellow at the Institute for Advanced Study in Princeton.