> 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.

What's the difference between doing that and just straight up proving what the exact value is?

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.

Indeed - a classic «upping the game» is to prove two bounds, then determine an exact value because you somehow get the bounds to intersect. https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1

Hell yeah, squeeze theorem! I was so enchanted when I first learned this one that everyone I knew also learned about the squeeze theorem.

Sorry, nothing substantial to add, I just got excited about it again

It cannot be harder, and could be a lot easier.

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?

What is positive about the best-case scenario being worse than we thought?

It would mean our best algorithms are closer to optimal than otherwise, which at least says positive things about our researchers.

Who knows? It could be n^2 log n, which when we're playing with the exponent basically is n^2.

Currently: 2.37187.

Not remotely close to 2.

What is the limit you would set for remotely close to 2?

The previous state of the art was 2.371866, this improvement brings it down by 0.000314. If you're moving increments that small 2 looks quite far away.