On the Hardness Hierarchy for the $O(n\sqrt{\log n})$ Complexity in the Word RAM

Dominik Kempa, Tomasz Kociumaka

In this work, we study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms that take $O(n\sqrt{\log n})$ time for instances described in $\Theta (n)$…