Combinatorial Boolean Matrix Multiplication in Near-Linear Time
Determine whether there exists a purely combinatorial algorithm for boolean matrix multiplication running in time O(n^{2+o(1)}) without using algebraic Strassen-like tensor methods.
Source: H. Yu, FOCS 2015: 109-119, 2015..
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
References
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.