We will have the pleasure to hear a talk from Marvin Künnemann (Max-Planck Institute for Informatics) about Nondeterministic Derandomization of Freivalds’ Algorithm.

This will happen in room “Philippe Flajolet (2017)” next Monday (Sept 16) at 10:30 (30 minutes + discussion)

Abstract:

Freivalds’ algorithm yields a surprisingly simple randomized O(n^2)-time solution for verifying whether an n x n matrix C is the product of two n x n matrices A and B. It is a long-standing open question whether this algorithm can be derandomized, i.e., whether matrix products can be verified deterministically in near-quadratic time. In this talk, we investigate a relaxation of this question: Can we derandomize Freivalds’ algorithm using additional nondeterministic guesses?

We discuss consequences of a positive or negative answer to this relaxed question and provide potential avenues towards resolving it. Furthermore, we present the partial algorithmic progress that distinguishing whether an integer matrix product is correct or contains between 1 and n erroneous entries can be performed in time (n^2) – interestingly, the difficult case of deterministic matrix product verification is not a problem of “finding a needle in the haystack”, but rather cancellation effects in the presence of many errors.

Our main technical contribution is a deterministic algorithm that corrects an integer matrix product containing at most t errors in time ( n^2 + t^2). To obtain this result, we show how to compute an integer matrix product with at most t nonzeroes in the same running time.

http://drops.dagstuhl.de/opus/volltexte/2018/9519/