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

• URL: http://arxiv.org/abs/2605.07289v1
• Date: Fri, 08 May 2026 05:55:42 GMT
• Title: On the Complexity of the Matching Problem of Regular Expressions with Backreferences
• Abstract summary: This paper investigates the fine-grained complexity of the string matching problem for regular expressions with backREWBs.<n>We present an $O(n2k-)$-time algorithm for $1$use REWBs, which significantly improves upon the recent $O(n2k-)$-time by Nogami and Terauchi (MFCS, 2025)<n>Our algorithm employs several techniques including suffix trees, transition monoidsEXes, factorization forest data structures, and periodicity of strings.
• Score: 0.7305019142196582
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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(n^{2k-ε})$ time for any $ε> 0$ under SETH. We also prove that this problem is \textbf{W[2]}-hard when parameterized by the length of the REWB expression, strengthening the previous \textbf{W[1]}-hardness. Moreover, we prove that this problem for $2$-use $2$-REWBs cannot be solved in $n^{1+o(1)}$ time unless the triangle detection problem can be solved in that time. On the algorithmic side, we present an $O(n \log^2 n)$-time algorithm for $1$-use REWBs, which significantly improves upon the recent $O(n^2)$-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.

Related papers

• Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations [10.282294365033785]
  We show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.<n>We present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems.
  arXiv  Detail & Related papers  (2025-05-01T22:17:11Z)
• Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
  We consider the two most common distances: Hamming distance in Pattern Matching with Mismatches and edit distance in Pattern Matching with Edits. We present quantum algorithms with a time complexity of $tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatches and $hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Edits.
  arXiv  Detail & Related papers  (2024-10-09T12:05:26Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Longest Common Substring and Longest Palindromic Substring in $\ ilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
  The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science. We present a quantum algorithm for both LCS and LPS working in the circuit model of computation.
  arXiv  Detail & Related papers  (2023-09-03T19:27:57Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Fast and Efficient Matching Algorithm with Deadline Instances [6.969116920943907]
  We introduce a market model with $mathrmdeadline$ first.<n>We present our two optimized algorithms (textscFastGreedy and textscFastPostponedGreedy)<n>At the same time, our algorithms run faster than the original two algorithms.
  arXiv  Detail & Related papers  (2023-05-15T05:21:20Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
  We give quantum algorithms for fundamental string problems with near-optimal query complexities and time complexities. These problems include Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
  arXiv  Detail & Related papers  (2021-10-19T02:32:18Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.