[Alta-Logic] Computer Science Invited Speaker - Pavel Hrubes November 23rd, 2009 at 12pm in ICT 616

[Robin Cockett]

Pavel Hrubes is visiting the university for Monday/Tuesday 23/24 November. 
We will be going to lunch with him after his talk if you wish to join us 
please do! 


                    Invited Speaker

***
     "Non-Commutative Arithmetic Circuits and the Sum of 
                      Squares Problem"
**
                       presented by		
	
                       Pavel Hrubes

**/                       Hosted by Theory Group

/*

*Date:*                Monday, November 23, 2009

*Time:*               12:00pm

*Location:         *ICT 616


*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.

</div>