We will study the problem of matrix-vector multiplication. In particular, we consider the case when the matrix is dense and structured (but the vector is arbitrary). We will study the arithmetic complexity of this operation with the goal of identifying when we can perform this operation in near-linear number of operations. This is a very fundamental problem that has many (practical) applications. While it is not possible to cover these applications, we will use two case studies to motivate our study: (1) error-correcting codes and (2) (single layer) neural networks.

Along the way, we will study some nice results that hold for matrix-vector multiplication but are perhaps not as well-known as they should be (or at least were not known to me a few years back!): as a bonus these results will illustrate why arithmetic complexity is a nice lens to study matrix-vector multiplication under.

The technical results will hinge on some close connections of a large class of structured matrices with polynomials (both structured and not) as well as fast algorithms for basic polynomials operations. This course will assume knowledge of basic linear algebra (matrices, vectors, notions of linear independence and rank of matrices and so on) and familiarity with fields. Familiarity with algorithms for basic operations on polynomials is a bonus but is not required.

See here for more info.