Topics will vary from semester to semester. See Computer Science Division announcements.

In classical information theory, information is stored and measured in bits, and all bits are equal in cost and value. In quantum information theory, information is stored in tensors, which vary considerably in their cost and value. Neither is properly understood. Matrix multiplication is the fundamental operation of linear algebra. In research on the complexity of matrix multiplication one confronts the same issue of cost and value of tensors. Historically, cost has been approached using tools from algebraic geometry and representation theory, while value has been approached using tools from analysis, probability, and combinatorics. I will present all these perspectives and attempt to bring them together. Nothing beyond undergraduate level mathematics will be assumed.

Plan I. History and background — matrix multiplication complexity, quantum information theory, and the role of tensors. Basic definitions regarding tensors. Other problems where cost and value of tensors arise (Fourier analysis, structure v. randomness, additive combinatorics).

II. Value — review of relevant probability and information theory. Measures of value and their uses. Strassen's functionals and their recent quantum analogs (work of Christandl, Vrana, and Zuiddam), including the relevant representation theory needed to define them. Work of Cohen and Moshkovitz on partition and analytic rank, and of Derksen on G-stable rank. Work of Chang, Derksen, Draisma and others on generic subrank. Measures of entanglement.

III. Cost — lower bounds for the complexity of matrix multiplication. Relevant representation theory and algebraic geometry needed to prove the lower bounds. Recent work on tensors of minimal cost. Connections to classical problems in linear algebra (spaces of commuting matrices, spaces of bounded rank). Recent work of Buczynska, Buczynski, Conner, Jelisiejew, Gesmundo, Harper, Huang, Landsberg, Mandziuk, and Sivic.

Class is meeting in Calvin Lab 116, Simons Institute

No time conflicts will be allowed

Repeat Rules