(Dense Structured) Matrix Vector Multiplication
Atri Rudra
(University at Buffalo, State University of New York).
Course Summary 
About the lecturer 
Location and schedule 
Materials

Assignment
We will study the problem of matrixvector 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 nearlinear 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) errorcorrecting codes and (2) (single layer) neural networks.
Along the way, we will study some nice results that hold for matrixvector multiplication but are perhaps not as wellknown 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 matrixvector 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.
About the lecturer:Atri Rudra is an Associate Professor of Computer Science and Engineering at University at Buffalo, State University of New York. Atri received his Bachelor's degree from the Indian Institute of Technology, Kharagpur, India in 2000 and his Ph.D. from University of Washington in 2007. From 2000 to 2002, he was a Research Staff Member at IBM India Research Lab, New Delhi, India. His research interests lie in theoretical computer science and in particular, theory of errorcorrecting codes, database algorithms, linear algebra algorithms, sublinear algorithms, computational complexity, finite field theory and applications. He is a recipient of an NSF CAREER award (2009), HP Labs Innovation Research Award (2010), ESA best paper award (2010), UB Exceptional Scholars  Young Investigator award (2011), PODS best paper awards (2012 and 2016), IBM Faculty Award (2013), UB SEAS Senior Teacher of the Year Award (2015) and SIGMOD Research Highlights (2016).
Location and schedule:MIMUW building, room 5440.



Materials
Lecture notes  tentative version
Assignment:problem set. Please submit the solutions through moodle (registration key PHDOPEN1718.2358) by Sunday June 17.