Arithmetic circuits and algebraic geometry

Seminar
Speaker
Dr. Klim Efremenko (University of California, Berkeley)
Date
31/12/2014 - 11:30 - 10:30Add to Calendar 2014-12-31 10:30:00 2014-12-31 11:30:00 Arithmetic circuits and algebraic geometry The goal of this talk is to show that natural questions in complexity theory raise very natural questions in algebraic geometry.    More precisely,  we will show how to adapt an approach introduced by Landsberg and  Ottaviani, called Young Flattening, to questions about arithmetic circuits. We will show that this approach generalizes the method of shifted partial derivatives introduced by Kayal to show lower bounds for shallow circuits.  We will also show how one can calculate shifted partial derivatives of the permanent using methods from homological algebra, namely by calculating a minimal free resolution of an ideal generated by partial derivatives.   I will not assume any previous knowledge about arithmetic circuits.   Joint work with J.M. Landsberg, H Schenck, J Weyman. Third floor seminar room אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Third floor seminar room
Abstract

The goal of this talk is to show that natural questions in complexity theory raise very natural questions in algebraic geometry. 

 

More precisely,  we will show how to adapt an approach introduced by Landsberg and  Ottaviani, called Young Flattening, to questions about arithmetic circuits. We will show that this approach generalizes the method of shifted partial derivatives introduced by Kayal to show lower bounds for shallow circuits. 

We will also show how one can calculate shifted partial derivatives of the permanent using methods from homological algebra, namely by calculating a minimal free resolution of an ideal generated by partial derivatives.

 

I will not assume any previous knowledge about arithmetic circuits.  

Joint work with J.M. Landsberg, H Schenck, J Weyman.

Last Updated Date : 24/12/2014