# On the Complexity of the Matching Problem of Regular Expressions with Backreferences

arXiv: https://arxiv.org/abs/2605.07289 · HTML: https://mlsanity.com/paper/2605.07289/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 70 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 12 of 12)

- [Popular conjectures imply strong lower bounds for dynamic problems](https://mlsanity.com/paper/1402.0054/) (2014)
- [Which Regular Expression Patterns are Hard to Match?](https://mlsanity.com/paper/1511.07070/) (2015)
- [The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds](https://mlsanity.com/paper/2311.10204/) (2023)
- [Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping (Extended Version)](https://mlsanity.com/paper/2401.12639/) (2024)
- [One-variable word equations in linear time](https://mlsanity.com/paper/1302.3481/) (2013)
- [Mind the Gap](https://mlsanity.com/paper/1503.07563/) (2015)
- [Deterministic Regular Expressions With Back-References](https://mlsanity.com/paper/1802.01508/) (2018)
- [Regular Expressions with Backreferences: Polynomial-Time Matching Techniques](https://mlsanity.com/paper/1903.05896/) (2019)
- [Sparse Regular Expression Matching](https://mlsanity.com/paper/1907.04752/) (2019)
- [Linear Matching of JavaScript Regular Expressions](https://mlsanity.com/paper/2311.17620/) (2023)
- [Efficient Matching of Some Fundamental Regular Expressions with Backreferences](https://mlsanity.com/paper/2504.18247/) (2025)
- [Hardness of Regular Expression Matching with Extensions](https://mlsanity.com/paper/2601.03020/) (2026)

## Abstract (arXiv)

ReDoS is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust computational resources of systems. Even quadratic-time behavior in matching engines has been exploited in successful attacks, as exemplified by major outages at Stack Overflow (2016) and Cloudflare (2019). These incidents motivate a fundamental question: Is it possible to construct matching engines that are provably efficient, running in (near-)linear time in the length of the input string? For classical regular expressions (REGEX), Thompson's construction yields a linear-time algorithm. However, practical engines support powerful features such as backreferences, which strictly extend the expressive power of REGEX but unfortunately increase the risk of ReDoS attacks. This paper investigates the fine-grained complexity of the string matching problem for regular expressions with backreferences (REWBs). Specifically, we consider r-use k-REWBs. On the hardness side, we show that the string matching problem for k-REWBs cannot be solved in O(n2k-ε) time for any ε > 0 under SETH. We also prove that this problem is W[2]-hard when parameterized by the length of the REWB expression, strengthening the previous W[1]-hardness. Moreover, we prove that this problem for 2-use 2-REWBs cannot be solved in n1+o(1) time unless the triangle detection problem can be solved in that time. On the algorithmic side, we present an O(n log2 n)-time algorithm for 1-use REWBs, which significantly improves upon the recent O(n2)-time algorithm by Nogami and Terauchi (MFCS, 2025). Our algorithm employs several techniques including suffix trees, transition monoids of REGEXes, factorization forest data structures, and periodicity of strings.