Haifa University - Dept. of CS Theory Seminar

Speaker : Amir Shpilka, Technion.

Title: "Reconstruction of depth-3 arithmetic circuits".

Date: Thursday, Feb. 14.

Place: Haifa U. Education Building, room 570.

Time: 12:15 - 13:30

Abstract:

We consider a fundamental problem in algebraic complexity, the circuit reconstruction problem: we are given a
black-box access to an arithmetic circuit and we have to find a small circuit computing the same polynomial.
Determining the complexity of the problem is an outstanding open question in algebraic complexity.

In this talk we shall give an algorithm for reconstructing depth 3 arithmetic circuits with bounded top fan-in.
This is the first algorithm that go beyond the well studied case of depth 2 circuits (polynomials computed by
depth 2 circuits are also known as sparse polynomials).

The talk is self contained and all notions will be explained. Some of the results are joint work with Zohar
Karnin (Technion).