> AFAIK the current theoretical lower bound still is 2 ... I don’t think anybody believes that 2 even remotely is a tight bound.
It's not "still". It's trivial to prove that 2 is the lowest possible value. Simply because you can't even read all the inputs in less than n^2 operations. So it's a tight lower bound for sure.
It's not a tight lower bound unless it's proven that no greater value could be a lower bound, and that's very much an open problem if I understand correctly.
Depending on the nature of the problem and the proof technique, sometimes it can be (from a little to much) easier to prove something is no greater than or no less than a certain bound than proving what exactly it is. For example it's trivial to prove using triangles that the square root of two is somewhere between 7/5 and 3/2 but proving exactly the value of root two is quite a lot harder.
Lots (well, relatively lots; this isn’t a research area with millions of practitioners) of people must have been looking at that problem ever since Strassen showed the exact value is less than 3 in 1969 (https://en.wikipedia.org/wiki/Strassen_algorithm), and there hasn’t been progress on moving that needle, so I doubt it’s even remotely easy, though.
To prove the exact value, you generally have to provide an algorithm that (provably) fulfills that value, and also prove that no other algorithm can possibly do better
It's very distressing to see this insightful and helpful comment[1] grayed out because of a pedandic argument about what "tight" means. The HN community used to be so much better than this.
[1] I'm sure everyone who clicked the downvote button thought it was obvious, but not everyone here has that level of intuition about big-O analysis. This isn't a math forum, we're all hackers here, right?
It's not "still". It's trivial to prove that 2 is the lowest possible value. Simply because you can't even read all the inputs in less than n^2 operations. So it's a tight lower bound for sure.