License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.56
URN: urn:nbn:de:0030-drops-95195
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9519/
Künnemann, Marvin
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
Abstract
Motivated by studying the power of randomness, certifying algorithms and barriers for fine-grained reductions, we investigate the question whether the multiplication of two n x n matrices can be performed in near-optimal nondeterministic time O~(n^2). Since a classic algorithm due to Freivalds verifies correctness of matrix products probabilistically in time O(n^2), our question is a relaxation of the open problem of derandomizing Freivalds' algorithm.
We discuss consequences of a positive or negative resolution of this problem and provide potential avenues towards resolving it. Particularly, we show that sufficiently fast deterministic verifiers for 3SUM or univariate polynomial identity testing yield faster deterministic verifiers for matrix multiplication. 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 O~(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 O~(sqrt{t} 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. This improves upon known deterministic output-sensitive integer matrix multiplication algorithms for t = Omega(n^{2/3}) nonzeroes, which is of independent interest.
BibTeX - Entry
@InProceedings{knnemann:LIPIcs:2018:9519,
author = {Marvin K{\"u}nnemann},
title = {{On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {56:1--56:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9519},
URN = {urn:nbn:de:0030-drops-95195},
doi = {10.4230/LIPIcs.ESA.2018.56},
annote = {Keywords: matrix product verification, certifying computation, fine-grained complexity and algorithms}
}
|
Keywords: |
|
matrix product verification, certifying computation, fine-grained complexity and algorithms |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
