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

Abstract

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)$ machine words ($\Theta (n\log n)$ bits). This complexity class, one of six hardness levels identified by Chan and Pătraşcu [SODA 2010], includes problems from several domains: 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 tasks (Orthogonal Range Counting, Orthogonal Segment Intersection Counting). We offer two main contributions: We establish new links between the above string problems and Dictionary Matching, a classic task solvable using the Aho-Corasick automaton. We restrict Dictionary Matching to instances with $\Theta (n)$ binary patterns of length $m=\Theta (\log n)$ each, and we prove that, unless these instances can be solved in $o(n\sqrt{\log n})$ time, the aforementioned string problems cannot be solved faster either. Via further reductions, we extend this hardness to Counting Inversions (a fundamental component in geometric algorithms) and thus to Orthogonal Range Counting and Orthogonal Segment Intersection Counting. This hinges on String Nesting, a new problem which is equivalent to Dictionary Matching and can be reduced to Counting Inversions in three steps. Together, our results unveil a single problem, with two equivalent formulations, that underlies the hardness of nearly all major problems currently occupying the $O(n\sqrt{\log n})$ level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. As an auxiliary outcome of our framework, we also prove that several central string problems can be efficiently reduced to their versions over the binary alphabet.

arXiv commentAccepted to SIAM Journal on Computing (special issue for STOC 2025)

References in corpus (12)

• Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
• Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space
• Wavelet Trees Meet Suffix Trees
• Resolution of the Burrows-Wheeler Transform Conjecture
• String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
• Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
• LZ-End Parsing in Compressed Space
• Lempel-Ziv Parsing in External Memory
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts
• Breaking the $O(n)$-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
• More on Change-Making and Related Problems
• Lempel-Ziv (LZ77) Factorization in Sublinear Time