Algebraic Complexity Theory studies the complexity of solving algebraic computational tasks using algebraic models of computation.
One major problem in this area is to prove lower bounds on the number of arithmetic operations required for computing explicit polynomials. This natural mathematical problem is the algebraic analog of the P vs. NP problem. It also has tight connections to other classical mathematical areas and to fundamental questions in complexity theory.
In this talk I will provide background and then present some recent progress in this line of study, particularly in the area of proving lower bounds for computing linear transformations.
Ben Lee Volk is a postdoctoral researcher at UT Austin. Previously, he was a postdoctoral scholar at Caltech. He obtained his Ph.D. from Tel Aviv University and his M.Sc. from the Technion, both under the supervision of Amir Shpilka. His research interests include complexity theory, and in particular the study of algebraic models of computation, as well as neighboring areas such as pseudorandomness, coding theory and combinatorics.