Near-optimal quantum algorithms for string problems
From MaRDI portal
Publication:6174814
DOI10.1007/s00453-022-01092-xarXiv2110.09696OpenAlexW4318215383MaRDI QIDQ6174814
Publication date: 17 August 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.09696
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing minimal and maximal suffixes of a substring
- On demand string sorting over unbounded alphabets
- Quantum pattern matching fast on average
- String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
- A faster algorithm computing string edit distances
- Lexicographically least circular substrings
- An optimal algorithm for computing the repetitions in a word
- Optimal canonization of all substrings of a string
- Optimal algorithms for computing the canonical form of a circular string
- Complexity measures and decision tree complexity: a survey.
- Dynamic and internal longest common substring
- Longest common substrings with \(k\) mismatches
- Longest common substring with approximately \(k\) mismatches
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- A Small Approximately Min-Wise Independent Family of Hash Functions
- Reconstructing Strings from Substrings with Quantum Queries
- Sublinear Space Algorithms for the Longest Common Substring Problem
- Longest Common Extensions in Trees
- Search via Quantum Walk
- Deterministic Sampling–A New Technique for Fast Pattern Matching
- Factorizing words over an ordered alphabet
- An O(n log n) algorithm for finding all repetitions in a string
- Quantum lower bounds for the collision and the element distinctness problems
- Computing Longest Common Substrings Via Suffix Arrays
- Uniquely Represented Data Structures for Computational Geometry
- Fast Lightweight Suffix Array Construction and Checking
- Adding range restriction capability to dynamic data structures
- Efficient randomized pattern-matching algorithms
- Fast canonization of circular strings
- Fast Pattern Matching in Strings
- Algorithms on Strings, Trees and Sequences
- Strengths and Weaknesses of Quantum Computing
- Jewels of Stringology
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
- Dynamic Orthogonal Range Searching on the RAM, Revisited
- On Minimal and Maximal Suffixes of a Substring
- Time-Space Trade-Offs for the Longest Common Substring Problem
- Quantum Algorithms for the Subset-Sum Problem
- Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- Repetition Detection in a Dynamic String
- Longest common substring made fully dynamic
- Quasi-Linear-Time Algorithm for Longest Common Circular Factor
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- Longest Lyndon Substring After Edit
- Linear-Time Algorithm for Long LCF with k Mismatches
- Locally Consistent Parsing for Text Indexing in Small Space
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Time-Efficient Quantum Walks for 3-Distinctness
- Uniqueness Theorems for Periodic Functions
- Internal Pattern Matching Queries in a Text and Applications
- More Applications of the Polynomial Method to Algorithm Design
- Faster Longest Common Extension Queries in Strings over General Alphabets
- Longest Common Substring with Approximately k Mismatches
- Minimal Suffix and Rotation of a Substring in Optimal Time
- Quantum Algorithms for the Triangle Problem
- Algorithms on Strings
- Quantum Walk Algorithm for Element Distinctness
- Fully Dynamic Orthogonal Range Reporting on RAM
- Nested Quantum Walks with Quantum Data Structures
- Quantum algorithms for computational geometry problems
- Approximating Longest Common Substring with k mismatches: Theory and Practice
- Free differential calculus. IV: The quotient groups of the lower central series
This page was built for publication: Near-optimal quantum algorithms for string problems
