k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
Title resolution pending
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
background 1
method 1
citation-polarity summary
years
2026 4verdicts
UNVERDICTED 4representative citing papers
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Defines cost-aware RAG with evidence cost tiers and shows static selectors are brittle while agentic LLM-based selection is promising but model-dependent.
The anti-lexicographic SUS-anchor achieves sampling densities less than 1% above the lower bound for alphabet size 4 and k=1, substantially outperforming bidirectional anchors.
citing papers explorer
-
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
k-REWB matching cannot be solved in O(n to the 2k minus epsilon) time under SETH, is W[2]-hard parameterized by expression length, and 2-use 2-REWBs require superlinear time unless triangle detection does; 1-use REWBs admit an O(n log squared n) algorithm.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
When Knowledge Is Not Free: Cost-Aware Evidence Selection in Retrieval-Augmented Generation
Defines cost-aware RAG with evidence cost tiers and shows static selectors are brittle while agentic LLM-based selection is promising but model-dependent.
-
The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme
The anti-lexicographic SUS-anchor achieves sampling densities less than 1% above the lower bound for alphabet size 4 and k=1, substantially outperforming bidirectional anchors.