4 ms·

On the off chance an expert reads this comment and feels like answering, is there a consensus opinion (or even just your opinion) on what the best result is lik

On the off chance an expert reads this comment and feels like answering, is there a consensus opinion (or even just your opinion) on what the best result is likely to be? Do people think O(n^2) is actually possible? Edit: shoulda read to the end, it says that Strassen says no.

phkahler 6y ago
I'm no expert, but IMHO it feels like a problem that might have O(n^2 log(n)) time complexity. That would be more satisfying than some arbitrary non-integer exponent.
- waynecochran 6y ago
  Get that n out of the exponent -- that is waay too slow. Maybe you meant O(n^3*log(2))? That exponent is definitely a constant.
  - btilly 6y ago
    We have better than that. I think that what was meant is O(n^2*log(n))
    - nightcracker 6y ago
      That isn't just what's meant, that's also what's written.
      - btilly 6y ago
        The way that it was written didn't disambiguate whether or not the log is part of the exponent. Putting the * in there disambiguated that.
        nightcracker 6y ago
        It doesn't. The multiplication is implied and it would have the same precedence as explicitly putting * there. So either both are ambiguous or neither is (and it isn't, the poster was just mistaken).
        btilly 6y ago
        I'm not sure why you think that it is implied. I know that I have a lot of math background, and my brain read that log(n) as part of the exponent. I figure that if I read it that way, you have to expect that others will as well.
        nightcracker 6y ago
        No matter how you read a^b log(c), the multiplication is implied. The original confusion is whether it's to be read as (a^b)log(c) or a^(b log(c)). a^b*log(c) simply removes the implied multiplication, but it does not change whether that should be read as (a^b)*log(c) or a^(b*log(c)) and thus does not resolve the original confusion.
  - jessriedel 6y ago
    I don't know if he edited his comment, but as it is currently written the log is not in the exponent under standard order of operations. Also, putting a constant factor like log(2) inside big-O notation is meaningless.
    - kadoban 6y ago
      Constant factors in exponents are _not_ meaningless. One of those cases where the rules-of-thumb bite you.
      - jessriedel 6y ago
        I didn't claim that. The log(2) term is multiplied, and that's implied by my use of "factor", which in this context is always understood to mean multiplicative factor.
        kadoban 6y ago
        You're correct. I think this comes down to confusion on the operator precedence. I read it as O(n^(3 log 2)) because otherwise it's kind of very obviously not correct (no way it's n^3, that's already known), but should have stated that, because according to usual notation/precedence it's not that.
jessriedel 6y ago
The impression I had is that many experts believe that no single algorithm A can achieve O(n^2), but there exists a sequence of algorithms A_i that achieve O(n^{2+d_i}), with d_i>0 getting arbitrarily small, but with the algorithms getting arbitrarily long and the constant overhead factors out front getting arbitrarily large. Unfortunately this was just word of mouth, and I might be misremembering.
- zests 6y ago
  This is what I choose to believe. Even if it is not true I will still believe it because it is so satisfying.
  - jessriedel 6y ago
    Yea. I've always wondered whether it was motivated purely by intuition about elegance, or whether there is another computational task that has been shown to have this feature. (The finite-length proof that an infinite tower of algorithms exist without them actually being specifiable in finite length would I guess require some Gödelian jiu jitsu?)
    - woopwoop 6y ago
      Hmm, I guess I don't get it. I feel like if you have such a sequence of algorithms A_i, you can "string them together" to get a single algorithm A which has the property that it has complexity O(n^{1 + epsilon}) for any epsilon > 0. Specifically, suppose we know that A_i requires time at most C_i + D_i n^{1 + 1/i}. Then there exists N_i such that, for any n >= N, C_i + D_i n^{1 + 1/i} >= C_{i+1} + n^{1 + 1/(i+1)}, and so can't we specify A by saying "if the input has size n where N_i <= n < N_{i+1}, perform A_i"?
      - zests 6y ago
        The problem is that each algorithm likely has a constant factor much larger than the previous. This does not matter for the runtime complexity of any individual algorithm but when you string them together the time complexity explodes.
sn41 6y ago
Strassen has shown that the bound is higher than n^2 using a tensor rank bound. [1] The exact exponent bound is usually called omega in the literature, and there are good estimates for the value of omega. It is also related to other quantities like Grothendieck constant [2]. [1] http://www.thi.informatik.uni-frankfurt.de/~jukna/Strassen-Vermeidung-von-Divisionen.pdf http://www.thi.informatik.uni-frankfurt.de/~jukna/Strassen-V... [2] https://arxiv.org/pdf/1711.04427.pdf https://arxiv.org/pdf/1711.04427.pdf

phkahler 6y ago

I'm no expert, but IMHO it feels like a problem that might have O(n^2 log(n)) time complexity. That would be more satisfying than some arbitrary non-integer exponent.

waynecochran 6y ago
Get that n out of the exponent -- that is waay too slow. Maybe you meant O(n^3*log(2))? That exponent is definitely a constant.
- btilly 6y ago
  We have better than that. I think that what was meant is O(n^2*log(n))
  - nightcracker 6y ago
    That isn't just what's meant, that's also what's written.
    - btilly 6y ago
      The way that it was written didn't disambiguate whether or not the log is part of the exponent. Putting the * in there disambiguated that.
      - nightcracker 6y ago
        It doesn't. The multiplication is implied and it would have the same precedence as explicitly putting * there. So either both are ambiguous or neither is (and it isn't, the poster was just mistaken).
        btilly 6y ago
        I'm not sure why you think that it is implied. I know that I have a lot of math background, and my brain read that log(n) as part of the exponent. I figure that if I read it that way, you have to expect that others will as well.
        nightcracker 6y ago
        No matter how you read a^b log(c), the multiplication is implied. The original confusion is whether it's to be read as (a^b)log(c) or a^(b log(c)). a^b*log(c) simply removes the implied multiplication, but it does not change whether that should be read as (a^b)*log(c) or a^(b*log(c)) and thus does not resolve the original confusion.
- jessriedel 6y ago
  I don't know if he edited his comment, but as it is currently written the log is not in the exponent under standard order of operations. Also, putting a constant factor like log(2) inside big-O notation is meaningless.
  - kadoban 6y ago
    Constant factors in exponents are _not_ meaningless. One of those cases where the rules-of-thumb bite you.
    - jessriedel 6y ago
      I didn't claim that. The log(2) term is multiplied, and that's implied by my use of "factor", which in this context is always understood to mean multiplicative factor.
      - kadoban 6y ago
        You're correct. I think this comes down to confusion on the operator precedence. I read it as O(n^(3 log 2)) because otherwise it's kind of very obviously not correct (no way it's n^3, that's already known), but should have stated that, because according to usual notation/precedence it's not that.

jessriedel 6y ago

The impression I had is that many experts believe that no single algorithm A can achieve O(n^2), but there exists a sequence of algorithms A_i that achieve O(n^{2+d_i}), with d_i>0 getting arbitrarily small, but with the algorithms getting arbitrarily long and the constant overhead factors out front getting arbitrarily large. Unfortunately this was just word of mouth, and I might be misremembering.

zests 6y ago
This is what I choose to believe. Even if it is not true I will still believe it because it is so satisfying.
- jessriedel 6y ago
  Yea. I've always wondered whether it was motivated purely by intuition about elegance, or whether there is another computational task that has been shown to have this feature. (The finite-length proof that an infinite tower of algorithms exist without them actually being specifiable in finite length would I guess require some Gödelian jiu jitsu?)
  - woopwoop 6y ago
    Hmm, I guess I don't get it. I feel like if you have such a sequence of algorithms A_i, you can "string them together" to get a single algorithm A which has the property that it has complexity O(n^{1 + epsilon}) for any epsilon > 0. Specifically, suppose we know that A_i requires time at most C_i + D_i n^{1 + 1/i}. Then there exists N_i such that, for any n >= N, C_i + D_i n^{1 + 1/i} >= C_{i+1} + n^{1 + 1/(i+1)}, and so can't we specify A by saying "if the input has size n where N_i <= n < N_{i+1}, perform A_i"?
    - zests 6y ago
      The problem is that each algorithm likely has a constant factor much larger than the previous. This does not matter for the runtime complexity of any individual algorithm but when you string them together the time complexity explodes.

sn41 6y ago

Strassen has shown that the bound is higher than n^2 using a tensor rank bound. [1] The exact exponent bound is usually called omega in the literature, and there are good estimates for the value of omega. It is also related to other quantities like Grothendieck constant [2]. [1] http://www.thi.informatik.uni-frankfurt.de/~jukna/Strassen-Vermeidung-von-Divisionen.pdf http://www.thi.informatik.uni-frankfurt.de/~jukna/Strassen-V... [2] https://arxiv.org/pdf/1711.04427.pdf https://arxiv.org/pdf/1711.04427.pdf