Computer Science/Discrete Mathematics Seminar III

Depth-3 arithmetic circuits compute polynomials that can be represented as sums of products of linear functions. In spite of their simple structure, we are far from understanding such circuits. In this talk we will focus on the reconstruction problem for depth-3 circuits, that have a constant number of multiplication gates. I.e., we have access to some unknown polynomial, that can be represented as a sum of a constant number of products of linear functions, and by asking for its values on (a small number of) inputs of our choice we would like to find a depth-3 circuit computing it. We will show how to reconstruct such depth-3 circuits in time exp(polylog(s)) , where s is the size of a depth-3 circuit computing the unknown polynomial. Our techniques rely on a theorem on the structure of zero depth-3 circuits and on a zero testing algorithm that it implies.