Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems (Q2701384): Difference between revisions

@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3093792486
@@ Property / OpenAlex ID: W3093792486 / rank @@
+Normal rank
@@ Property / cites work @@
+A faster algorithm computing string edit distances
+Normal rank
@@ Property / cites work @@
+Oblivious string embeddings and edit distance approximations
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
+Normal rank
@@ Property / cites work @@
+Q4607964
@@ Property / cites work: Q4607964 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
+Normal rank
@@ Property / cites work @@
+Longest common substring made fully dynamic
@@ Property / cites work: Longest common substring made fully dynamic / rank @@
+Normal rank
@@ Property / cites work @@
+Sublinear Space Algorithms for the Longest Common Substring Problem
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
+Normal rank
@@ Property / cites work @@
+Quantum Walk Algorithm for Element Distinctness
@@ Property / cites work: Quantum Walk Algorithm for Element Distinctness / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum verification of matrix products
@@ Property / cites work: Quantum verification of matrix products / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228473
@@ Property / cites work: Q4228473 / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum Algorithms for the Triangle Problem
@@ Property / cites work: Quantum Algorithms for the Triangle Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
+Normal rank
@@ Property / cites work @@
+String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
+Normal rank
@@ Property / cites work @@
+Reconstructing Strings from Substrings with Quantum Queries
+Normal rank
@@ Property / cites work @@
+Q3410550
@@ Property / cites work: Q3410550 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant factor approximations to edit distance on far input pairs in nearly linear time
+Normal rank
@@ Property / cites work @@
+Constant-factor approximation of near-linear edit distance in near-linear time
+Normal rank
@@ Property / cites work @@
+Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
+Normal rank
@@ Property / cites work @@
+Q5092465
@@ Property / cites work: Q5092465 / rank @@
+Normal rank
@@ Property / cites work @@
+On computing the length of longest increasing subsequences
+Normal rank
@@ Property / cites work @@
+Tight Ω(<i>n</i>lg<i>n</i>) lower bound for finding a longest increasing subsequence
+Normal rank
@@ Property / cites work @@
+Q5417608
@@ Property / cites work: Q5417608 / rank @@
+Normal rank
@@ Property / cites work @@
+Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
+Normal rank
@@ Property / cites work @@
+Q4819589
@@ Property / cites work: Q4819589 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002773
@@ Property / cites work: Q3002773 / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic algorithms for LIS and distance to monotonicity
+Normal rank
@@ Property / cites work @@
+Search via Quantum Walk
@@ Property / cites work: Search via Quantum Walk / rank @@
+Normal rank
@@ Property / cites work @@
+Estimating the Longest Increasing Sequence in Polylogarithmic Time
+Normal rank
@@ Property / cites work @@
+Concentration of Measure for the Analysis of Randomized Algorithms
+Normal rank
@@ Property / cites work @@
+Quantum lower bounds for the collision and the element distinctness problems
+Normal rank
@@ Property / cites work @@
+Q3002756
@@ Property / cites work: Q3002756 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002755
@@ Property / cites work: Q3002755 / rank @@
+Normal rank
@@ Property / cites work @@
+An Erdős-Rényi law with shifts
@@ Property / cites work: An Erdős-Rényi law with shifts / rank @@
+Normal rank
@@ Property / cites work @@
+Strengths and Weaknesses of Quantum Computing
@@ Property / cites work: Strengths and Weaknesses of Quantum Computing / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2701384