3 ms·

As expected: closer, but not much closer. FTA: “we give a new bound of ω<2.371866 […]. Our result breaks the lower bound of 2.3725” AFAIK the current theoretic

As expected: closer, but not much closer. FTA: “we give a new bound of ω<2.371866 […]. Our result breaks the lower bound of 2.3725” AFAIK the current theoretical lower bound still is 2, so that’s only 600-ish more such steps to get there. On the positive side, I don’t think anybody believes that 2 even remotely is a tight bound.

bravura 3y ago
What is positive about the best-case scenario being worse than we thought?
- Filligree 3y ago
  It would mean our best algorithms are closer to optimal than otherwise, which at least says positive things about our researchers.
JohnKemeny 3y ago
Currently: 2.37187. Not remotely close to 2. What is the limit you would set for remotely close to 2?
- deleted 3y ago
  [deleted]
- eigenket 3y ago
  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.
- deleted 3y ago
  [deleted]
light_hue_1 3y ago
> 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.
- cwillu 3y ago
  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.
  - Asraelite 3y ago
    What's the difference between doing that and just straight up proving what the exact value is?
    - Someone 3y ago
      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 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.
    - seanhunter 3y ago
      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.
      - pletnes 3y ago
        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 https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1
        burnished 3y ago
sudosysgen 3y ago
Who knows? It could be n^2 log n, which when we're playing with the exponent basically is n^2.

bravura 3y ago

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

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

JohnKemeny 3y ago

Currently: 2.37187. Not remotely close to 2. What is the limit you would set for remotely close to 2?

deleted 3y ago
[deleted]
eigenket 3y ago
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.
deleted 3y ago
[deleted]

light_hue_1 3y ago

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

cwillu 3y ago
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.
- Asraelite 3y ago
  What's the difference between doing that and just straight up proving what the exact value is?
  - Someone 3y ago
    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 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.
  - seanhunter 3y ago
    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.
    - pletnes 3y ago
      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 https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1
      - burnished 3y ago

sudosysgen 3y ago

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