|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Non-commutative arithmetic computation|
|Affiliation:||Herbert H. Maass Professor, School of Mathematics|
|Date:||Tuesday, February 11|
|Time/Room:||10:30am - 12:30pm/S-101|
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.