Skip to Content

Palmer Mebane

Picture of Palmer Mebane.

Thesis

Uniquely Solvable Puzzles and Fast Matrix Multiplication

Advisor
Michael Orrison
Second Reader(s)
Nicholas Pippenger

Abstract

In 2003 Cohn and Umans introduced a new group-theoretic framework for doing fast matrix multiplications, with several conjectures that would imply the matrix multiplication exponent $\omega$ is 2. Their methods have been used to match one of the fastest known algorithms by Coppersmith and Winograd, which runs in $O(n^{2.376})$ time and implies that $\omega \leq 2.376$. This thesis discusses the framework that Cohn and Umans came up with and presents some new results in constructing combinatorial objects called uniquely solvable puzzles that were introduced in a 2005 follow-up paper, and which play a crucial role in one of the $\omega = 2$ conjectures.

Proposal

Fast Multiplication of Arbitrary and Structured Matrices via Group Algebras

Additional Materials

Poster