Avi Wigderson
Institute for Advanced Study; Faculty, School of Mathematics
February 11, 2014
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.

For more videos, visit [ Ссылка ]

свернуть