Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n^{3} * (log log n)$^{2} / (w * (log n)^{7}/{6}))

Space Complexity

words

()

Description

Approximate?

Exact

Randomized?

Yes, Las Vegas

Model of Computation

Word RAM with word size w > log n

Year

2009

Reference

https://ieeexplore.ieee.org/abstract/document/5438580