Worst-Case to Average-Case Reductions for Matrix

Multiplication via Additive Combinatorics

Author: McNichols, Nia M.

Year: 2023

Degree: Senior thesis (Major)

Advisor: Umans, Christopher M.

Committee Member: None, None

Option: Computer Science

DOI: 10.7907/4xz0-v816

Abstract

In the field of average-case complexity, we are concerned with how an algorithm performs on an average input, rather than the classical worst-case analysis. Of particular interest are worst-case to average-case reductions, that is transforming an algorithm that works on some fraction of inputs into a probabilistic one that works on all inputs. Building on recent results in the field, we present a framework for average-case matrix multiplication algorithms. Explicitly, our framework provides a transformation for algorithms running in time T(n) that work on a small fraction of inputs into ones running in time Õ(T(n)) that work on all inputs, even in the case when this fraction rapidly tends to 0. Moreover, our framework requires fewer non-trivial results than similar methods, at the cost of minor asymptotic losses.

Files