Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Non-commutative Computation (and More)
event speaker icon
Avi Wigderson (Institute for Advanced Study, Princeton)
event date icon
Wednesday, 25.12.2013, 12:30
event location icon
Room 337-8 Taub Bld.
I will survey what is known about the complexity of arithmetic circuits computing polynomials and rational functions with non-commuting variables, focusing on recent results and open problems. Strangely enough, some elementary questions in commutative algebra seem to hold the key both to new lower bounds and new algorithms. The talk is mainly based on several papers with Pavel Hrubes and Amir Yehudayoff.