Personal tools
You are here: Home Events Circuit Lower Bounds, Meta-Algorithms and Algebraic Computation

Circuit Lower Bounds, Meta-Algorithms and Algebraic Computation

Here is the talk's abstract:

 

In this talk I will explore the connection between proving circuit lower bounds and giving efficient meta-algorithms that solve fundamental problems about these circuits. I will focus on this phenomena as it happens in the algebraic setting. Here this centers around the problem of polynomial identity testing and the question of proving arithmetic circuit lower bounds, for example for the permanent polynomial. The talk will be biased in the sense that I will take the opportunity to revisit some of the main result that were obtained during my postdoc here in Edinburgh in collaboration with Rahul Santhanam.

Document Actions