Arithmetic Circuits, Structured Matrices and (not so) Deep Learning
This survey presents a necessarily incomplete (and biased) overview of
results at the intersection of arithmetic circuit complexity, structured
matrices and deep learning. Recently there has been some research activity in
replacing unstructured weight matrices in neural networks by structured ones
(with the aim of reducing the size of the corresponding deep learning models).
Most of this work has been experimental and in this survey, we formalize the
research question and show how a recent work that combines arithmetic circuit
complexity, structured matrices and deep learning essentially answers this
question.
  This survey is targeted at complexity theorists who might enjoy reading about
how tools developed in arithmetic circuit complexity helped design (to the best
of our knowledge) a new family of structured matrices, which in turn seem
well-suited for applications in deep learning. However, we hope that folks
primarily interested in deep learning would also appreciate the connections to
complexity theory.