On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM

In this work, we study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms taking O(nλlogn) time for instances described in (n) machine words (i.e., (nlogn) bits). The word RAM model nowadays serves as the default model of computation for sequential algorithms, and understanding its limitations lies at the core of theoretical computer science. The class of problems solvable in O(nλlogn) time is one of the six levels of hardness listed in the seminal paper of Chan and PÇ traşcu [SODA 2010]. According to the current state of knowledge, this class characterizes problems from several domains, including counting inversions, string processing problems (BWT Construction, LZ77 Factorization, Longest Common Substring, Batched Longest Previous Factor Queries, Batched Inverse Suffix Array Queries), and computational geometry problems (Orthogonal Range Counting, Orthogonal Segment Intersection). Our contribution is twofold: We present several new connections between the aforementioned string problems and an old Dictionary Matching problem, which asks whether a given text contains (an exact occurrence of) at least one among the given patterns. This is a classical problem with a solution based on the Aho-Corasick automaton dating back to 1975. In this work, we restrict Dictionary Matching to instances with O(n) binary patterns of length m=O(logn), short enough to be stored using O(1) machine words each, and we prove that, unless this problem can be solved faster than the current bound of O(nλlogn), most fundamental string problems cannot be solved faster either. With further reductions, we extend this hierarchy beyond string problems, proving that computational tasks like counting inversions - a fundamental component in geometric algorithms - inherit this hardness. This, in turn, establishes the hardness of Orthogonal Range Counting and Orthogonal Segment Intersection. The key to extending our results to other domains is a surprising equivalent characterization of Dictionary Matching in terms of a new problem we call String Nesting, which, through a chain of three more reductions, can be solved by counting inversions. Put together, our results unveil a single hard problem, with two different but equivalent formulations, that underlies the hardness of nearly all known major problems, coming from different domains, currently occupying the O(nλlogn) level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. Many of our reductions hold even for simpler versions of basic problems, such as determining the parity of the number of phrases in the LZ77 factorization or the number of runs in the BWT. This yields stronger results that can be used to design future reductions more easily. As an auxiliary outcome of our framework, we also prove that several central string problems in the RAM model do not get easier when limited to strings over the binary alphabet. Our reductions to the binary case simplify the currently fastest algorithms for many classical problems, including LZ77 Factorization and Longest Common Substring.