Abstract
A homogeneous depth three circuit C computes a polynomial f = T_1 + T_2 + ... + T_s, where each T_i is a product of d linear forms in n variables. Given black-box access to f, can we efficiently reconstruct (i.e. proper learn) a homogeneous depth three circuit computing f? Learning homogeneous depth three circuits efficiently is stated as an open problem in a work by Klivans and Shpilka (COLT 2003). This is a highly interesting and challenging problem as poly(n,d,s) time learning for homogeneous depth three circuits implies sub-exponential time learning for general arithmetic circuits. We give a randomized poly(n,d,s) time algorithm to reconstruct non-degenerate homogeneous depth three circuits, for n > (3d)^2 and s < (n/3d)^{d/3}. The algorithm works over any field F, provided char(F) = 0 or greater than ds^2, and univariate polynomial factorization over F can be done efficiently. Loosely speaking, a circuit C is non-degenerate if the dimension of the partial derivative space of f equals the sum of the dimensions of the partial derivative spaces of the terms T_1,...,T_s. In this sense, the terms are ``independent'' of each other in a non-degenerate circuit. A random homogeneous depth three circuit (where the coefficients of the linear forms are chosen according to the uniform distribution or any other reasonable distribution) is almost surely non-degenerate. Previous learning algorithms for homogeneous depth three circuits are either improper (with an exponential dependence on d), or they work for constant s (with a doubly exponential dependence on s). Our algorithm hinges on a decomposition of the partial derivative space of f into irreducible invariant subspaces under the action of a shifted differential operator space. The decomposition then leads to the terms of C. To our knowledge, this is the first time the shifted partial derivative operator has been used to make progress on reconstruction algorithms. The technique may also find applications in reconstruction of other circuit classes. Based on joint work with Neeraj Kayal.