Boolean Matrix Multiplication (BMM) and Triangle Detection
One of FMM algorithms that have reduced
The next question is, can we find a fast combinatorial algorithm?
- What is a combinatorial algorithm? Not well defined, but it is an algorithm that does not use techniques of FMM
- What is a fast combinatorial algorithm? Similarly to FMM, the algorithm that runs in
for some . Note that it is not equivalent to sub-polynomial algorithms with runtime of !
Boolean Matrix Multiplication (BMM) definition
Clearly, BMM seems to be computationally easier than general FMM, or at least not harder, so the CS community focused on finding a combinatorial
Existing combinatorial(!) algorithms are
- Yu (2015) -
- Abboud, Fischer, Kelley, Lovett, and Meka (2024) -
Both of these are , not
Non-existence of a combinatorial BMM algorithm hypothesis
What does this hypothesis mean for the CS researchers?
- If the community has decided to accept such a hypothesis, it means that it is likely (but not guaranteed) that in order to disprove the hypothesis, we need to invent new algorithmic techniques and apply them to said problem. So it might be a good idea not to work on solving such problems until new algorithmic techniques are discovered.
- Hypothesized lower bounds open the option of proving conditional lower bounds for other problems, based (conditioned) on the correctness of the hypothesis.
- Often, while the problem is hard for general inputs, it is possible that the problem is easier to solve on restricted families of inputs. Moreover, solving the problem on restricted families of inputs could provide insight into how to improve the algorithms for the general case, or maybe how to prove that the hypothesis is correct (if some restricted input families turn out to be too hard).
Further on, we will use the following notation
Triangle Detection Problem
Input
Output
Solution
Equivalence of TD and BMM theorem
This algorithms has a couple of problems
doesn’t locate triangles, it detects their existence(!) - Worst-case runtime is:
iterations of filling and each iteration is at least - in total
Now to the second problem, finding the triangle instead of just detecting it!