nd At STOC 2025, Duan et al. won a Best Paper award for…
0 reactions
nd
At STOC 2025, Duan et al. won a Best Paper award for "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." They successfully broke the 65-year-old O(m + n log n) bound established by Dijkstra, bringing the complexity for sparse directed graphs down to O(m log\^(2/3) n) in the comparison-addition model.
We often see these massive theoretical breakthroughs in TCS, but it can take years (or decades) before anyone attempts to translate the math into practical, running code, especially when the new bounds rely on fractional powers of logs that hide massive constants.
I found an experimental repository that actually implements this paper in C99, proving that the theoretical speedup can be made practical:
Repo: https://github.com/danalec/DMMSY-SSSP
Paper: https://arxiv.org/pdf/2504.17033
To achieve this, the author implemented the paper's recursive subproblem decomposition to bypass the global priority queue (the traditional sorting bottleneck). They combined this theoretical framework with aggressive systems-level optimizations: a cache-optimized Compressed Sparse Row (CSR) layout and a zero-allocation workspace design.
The benchmarks are remarkable: on graphs ranging from 250k to 1M+ nodes, the implementation demonstrates >20,000x speedups over standard binary heap Dijkstra implementations. The DMMSY core executes in roughly \~800ns for 1M nodes.
It's fascinating to see a STOC Best Paper translated into high-performance systems code so quickly. Has anyone else looked at the paper's divide-and-conquer procedure? I'm curious if this recursive decomposition approach will eventually replace priority queues in standard library graph implementations, or if the memory overhead is too steep for general-purpose use.
#technology LPT: Let Every Important Decision Pass Through a Night of Sleep Before You Make It Final
If you are angry, hurt, anxious, or even overly excited, resist the urge to decide immediately. Give the decision one full night of sleep before acting on it.
Sleep is not merely rest; it restores perspective. Emotional intensity naturally declines after proper rest, while rational thinking becomes stronger. What feels urgent and irreversible late at night often appears clearer and more balanced in the morning.
If the choice still feels right after you wake up, move forward with confidence. If it changes, you have protected yourself from acting on a temporary emotional state. Major decisions deserve a rested mind.
This prevents us from making impulsive decisions in most cases.
#entertainment
At STOC 2025, Duan et al. won a Best Paper award for "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." They successfully broke the 65-year-old O(m + n log n) bound established by Dijkstra, bringing the complexity for sparse directed graphs down to O(m log\^(2/3) n) in the comparison-addition model.
We often see these massive theoretical breakthroughs in TCS, but it can take years (or decades) before anyone attempts to translate the math into practical, running code, especially when the new bounds rely on fractional powers of logs that hide massive constants.
I found an experimental repository that actually implements this paper in C99, proving that the theoretical speedup can be made practical:
Repo: https://github.com/danalec/DMMSY-SSSP
Paper: https://arxiv.org/pdf/2504.17033
To achieve this, the author implemented the paper's recursive subproblem decomposition to bypass the global priority queue (the traditional sorting bottleneck). They combined this theoretical framework with aggressive systems-level optimizations: a cache-optimized Compressed Sparse Row (CSR) layout and a zero-allocation workspace design.
The benchmarks are remarkable: on graphs ranging from 250k to 1M+ nodes, the implementation demonstrates >20,000x speedups over standard binary heap Dijkstra implementations. The DMMSY core executes in roughly \~800ns for 1M nodes.
It's fascinating to see a STOC Best Paper translated into high-performance systems code so quickly. Has anyone else looked at the paper's divide-and-conquer procedure? I'm curious if this recursive decomposition approach will eventually replace priority queues in standard library graph implementations, or if the memory overhead is too steep for general-purpose use.
#technology LPT: Let Every Important Decision Pass Through a Night of Sleep Before You Make It Final
If you are angry, hurt, anxious, or even overly excited, resist the urge to decide immediately. Give the decision one full night of sleep before acting on it.
Sleep is not merely rest; it restores perspective. Emotional intensity naturally declines after proper rest, while rational thinking becomes stronger. What feels urgent and irreversible late at night often appears clearer and more balanced in the morning.
If the choice still feels right after you wake up, move forward with confidence. If it changes, you have protected yourself from acting on a temporary emotional state. Major decisions deserve a rested mind.
This prevents us from making impulsive decisions in most cases.
#entertainment
| 4,000 mlx | |
| 4 | |
| 0 |