HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm

Abstract : We design two nondeterministic algorithms for matrix multiplication. Both algorithms are based on derandomization of Freivalds’ algorithm for verification of matrix products. The first algorithm works with real numbers and its time complexity on Real RAMs is O(n2logn). The second one is of the same complexity, works with integer matrices on a unit cost RAM with numbers whose size is proportional to the size of the largest entry in the underlying matrices. Our algorithms bring new ideas into the design of matrix multiplication algorithms and open new avenues for their further development. The results pose exciting questions concerning the relation of the complexity of deterministic versus nondeterministic algorithms for matrix multiplication, and complexity of integer versus real matrices multiplication.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Thursday, November 24, 2016 - 10:49:35 AM
Last modification on : Wednesday, November 18, 2020 - 7:20:08 PM
Long-term archiving on: : Monday, March 20, 2017 - 4:12:09 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Jiří Wiedermann. Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.123-135, ⟨10.1007/978-3-662-44602-7_11⟩. ⟨hal-01402036⟩



Record views


Files downloads