Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication

Matthew Anderson, Vu Le
7/12/2023
cs.CCcs.AIcs.DS

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show that these puzzles are efficiently verifiable, which remains an open question for general SUSPs. We also show that individual simplifiable SUSPs can achieve the same strength of bounds on the matrix multiplication exponent $ω$ that infinite families of SUSPs can. We report on the construction, by computer search, of larger SUSPs than previously known for small width. This, combined with our tighter analysis, strengthens the upper bound on the matrix multiplication exponent from $2.66$ to $2.505$ obtainable via this computational approach, and nears the results of the handcrafted constructions of Cohn et al.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{anderson2023efficientlyverifiable,
  title  = {Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication},
  author = {Matthew Anderson and Vu Le},
  year   = {2023},
  eprint = {2307.06463},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2307.06463v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2307.06463.svg)](https://codeofpaper.com/paper/2307.06463)

Discussion