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

arXiv: https://arxiv.org/abs/2206.12490 · HTML: https://mlsanity.com/paper/2206.12490/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 24 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [Recent Advances in Convolutional Neural Networks](https://mlsanity.com/paper/1512.07108/) (2015)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Tunable Efficient Unitary Neural Networks (EUNN) and their application to RNNs](https://mlsanity.com/paper/1612.05231/) (2016)
- [Structured Transforms for Small-Footprint Deep Learning](https://mlsanity.com/paper/1510.01722/) (2015)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [Learning Compressed Transforms with Low Displacement Rank](https://mlsanity.com/paper/1810.02309/) (2018)
- [Theoretical Properties for Neural Networks with Weight Matrices of Low Displacement Rank](https://mlsanity.com/paper/1703.00144/) (2017)
- [Fast Approximation of Rotations and Hessians matrices](https://mlsanity.com/paper/1404.7195/) (2014)
- [Kronecker Products, Low-Depth Circuits, and Matrix Rigidity](https://mlsanity.com/paper/2102.11992/) (2021)

## Built on by (most cited first, 1 of 1)

- [Symmetry-Based Structured Matrices for Efficient Approximately Equivariant Networks](https://mlsanity.com/paper/2409.11772/) (2024)

## Abstract (arXiv)

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.