4 ms·

> 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

> 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
        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
  - layer8 3y ago
    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
ajross 3y ago
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?

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
      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
- layer8 3y ago
  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

ajross 3y ago

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?