Boolean Matrix Multiplication (Combinatorial)
Matrix multiplication of two boolean matrices (i.e. where all entries are in and addition is mod 2). Here, only "combinatorial" algorithms are considered.
Parameters
- : dimension of square matrix
Filters
Computational Model
Randomization
Approximation
Algorithms Table
Displaying 7 of 7 algorithms
| See more | ||||
|---|---|---|---|---|
| 2018 | O(n^3 / log^2.25 n) | |||
| Chan | 2015 | O(n^3 * (log log n)^3 / log^3 n) | ||
| Chan | 2015 | O(n^3 * (log w)^3 / (w * log^2 n)) | ||
| Yu | 2015 | O(n^3*poly(log log n)/log^4 n) | ||
| Bansal, Williams | 2009 | O(n^3 * (log log n)^2 / log^2.25 n) | ||
| Bansal, Williams | 2009 | O(n^3 * (log log n)^2 / (w * (log n)^7/6)) | ||
| Method of Four Russians | 1970 | O(n^3/(log n)^2) |
Reductions Table
Insuffient Data to display table
Other relevant algorithms
Insuffient Data to display table