Theory of Computing ------------------- Title : Learning Restricted Models of Arithmetic Circuits Authors : Adam Klivans and Amir Shpilka Volume : 2 Number : 10 Pages : 185-206 URL : https://theoryofcomputing.org/articles/v002a010 Abstract -------- We present a polynomial time algorithm for learning a large class of algebraic models of computation. We show that any arithmetic circuit whose partial derivatives induce a low-dimensional vector space is exactly learnable from membership and equivalence queries. As a consequence, we obtain polynomial-time algorithms for learning restricted algebraic branching programs as well as noncommutative set-multilinear arithmetic formulae. In addition, we observe that the algorithms of Bergadano et al. (1996) and Beimel et al. (2000) can be used to learn depth-3 set-multilinear arithmetic circuits. Previously only versions of depth-2 arithmetic circuits were known to be learnable in polynomial time. Our learning algorithms can be viewed as solving a generalization of the well known *polynomial interpolation problem* where the unknown polynomial has a succinct representation. We can learn representations of polynomials encoding *exponentially* many monomials. Our techniques combine a careful algebraic analysis of the partial derivatives of arithmetic circuits with "multiplicity automata" learning algorithms due to Bergadano et al. (1997) and Beimel et al. (2000).