Arithmetic Circuits, Structured Matrices and (not so) Deep Learning

This survey shows how concepts in arithmetic circuit complexity and structured matrices can be used to solve a (theoretical) problem motivated by practical applications in machine learning (especially deep learning). Since each of the areas of arithmetic (circuit) complexity, structured matrices and deep learning have been explored in great depth and this survey clearly cannot do any justice to all the great work in each of the these areas, we will spend most of the introduction clarifying what this survey is not about. Algebraic circuit complexity or more generally algebraic complexity theory [11] studies the power of algebraic algorithms (as opposed to the Turing machine/RAM model). The arithmetic circuit model (or the straight-line programs) are one of the standard models of computation in algebraic complexity theory [11, Chapter 4]. In this survey we will ignore pretty much everything in this literature except for results on the arithmetic circuit complexity of the linear map i.e. functions of the form x Wx (where x is a vector over some field F and W is a matrix over the same field) [11, Chapter 13]. We would like to stress that this survey will only scratch the surface of the literature on the algebraic circuit complexity of the linear map. Just to give a sense of the breadth of this seemingly'specialized' topic, we remark that the study of matrix rigidity [22], which has seen a lot of recent research activity [1, 2, 3, 19, 10], is a part of this topic. We note that originally, the topic of matrix rigidity was proposed by Valiant [42] as a way to prove super-linear lower bounds, by constructing matrices that are rigid. However, our goal in this survey is to prove upper bounds-i.e.