Non-commutative arithmetic computation

Computer Science/Discrete Mathematics Seminar II
Topic:Non-commutative arithmetic computation
Speaker:Avi Wigderson
Affiliation:Herbert H. Maass Professor, School of Mathematics
Date:Tuesday, February 11
Time/Room:10:30am - 12:30pm/S-101
Video Link:

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.