3 ms·

O(m log^2/3 n) !!! What a triumph.

supernetworks_ 1y ago
https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033 We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
- hinkley 1y ago
  log^2/3 might be the weirdest component I’ve ever seen in a complexity formula.
  - deleted 1y ago
    [deleted]
  - bawolff 1y ago
    I still think matrix multiplication's O(n^2.371339) is super weird.
    - adgjlsfhk1 1y ago
      Matrix multiplication definitely should be O(n^(2+o(1))).
  - adgjlsfhk1 1y ago
    for about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm. Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3). Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.
    - Sniffnoy 1y ago
      Hey the asterisks in your reply got read as formatting so it's ended up messed-up.
      - adgjlsfhk1 1y ago
        oops. fixed.
    - hinkley 1y ago
      Are BigInteger multiplications in logn² now or do they still have weird terms in them?
      - adgjlsfhk1 1y ago
        down to nlogn
  - jojomodding 1y ago
    I'm continually amazed by the asymptotic complexity of union-find, which is O(alpha(n)), where alpha(x) is the inverse of the Ackermann function (and n the number of sets you union). In other words, O(6) or so as long as your inputs fit into the observable universe.
    - hinkley 1y ago
      There's definitely a divide on who sees what sort of algorithms. The subject of this article is in Graph Theory space, which a lot of us get even without trying (I dabbled in TSP for a while because it's a difficult distributed programming problem and I wanted to explore the space for that reason). But if you're not implementing AI or game engines, some of the linear algebra space may be a road less traveled.

https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033 We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

hinkley 1y ago
log^2/3 might be the weirdest component I’ve ever seen in a complexity formula.
- deleted 1y ago
  [deleted]
- bawolff 1y ago
  I still think matrix multiplication's O(n^2.371339) is super weird.
  - adgjlsfhk1 1y ago
    Matrix multiplication definitely should be O(n^(2+o(1))).
- adgjlsfhk1 1y ago
  for about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm. Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3). Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.
  - Sniffnoy 1y ago
    Hey the asterisks in your reply got read as formatting so it's ended up messed-up.
    - adgjlsfhk1 1y ago
      oops. fixed.
  - hinkley 1y ago
    Are BigInteger multiplications in logn² now or do they still have weird terms in them?
    - adgjlsfhk1 1y ago
      down to nlogn
- jojomodding 1y ago
  I'm continually amazed by the asymptotic complexity of union-find, which is O(alpha(n)), where alpha(x) is the inverse of the Ackermann function (and n the number of sets you union). In other words, O(6) or so as long as your inputs fit into the observable universe.
  - hinkley 1y ago
    There's definitely a divide on who sees what sort of algorithms. The subject of this article is in Graph Theory space, which a lot of us get even without trying (I dabbled in TSP for a while because it's a difficult distributed programming problem and I wanted to explore the space for that reason). But if you're not implementing AI or game engines, some of the linear algebra space may be a road less traveled.