A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

• URL: http://arxiv.org/abs/2310.00966v1
• Date: Mon, 2 Oct 2023 08:14:34 GMT
• Title: A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings
• Authors: Tzu-Ching Lee and Han-Hsuan Lin
• Abstract summary: We give a sublinear quantum algorithm for the longest common (LCS) problem on the run-length encoded (RLE) inputs. Our algorithm costs $tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ time, where $n$ and $tilden$ are the encoded and decoded length of the inputs, respectively.
• Score: 0.951828574518325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs $\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$ time, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a $\Omega(n/\log^2n)$ lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.

Related papers

• Quantum Algorithm for the Multiple String Matching Problem [0.0]
  We consider a sequence of $m$ strings, denoted by $S$, which we refer to as a dictionary. The objective is to identify all instances of strings from the dictionary within the text. We propose a quantum algorithm with $O(n+sqrtmLlog nlog n)$ query complexity and $O(n+sqrtmLlog n)=O*(n+sqrtmL)$ time complexity.
  arXiv  Detail & Related papers  (2024-11-22T10:50:43Z)
• Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings [0.8057006406834466]
  We give a near-optimal quantum algorithm for the longest common (LCS) problem between two run-length encoded (RLE) strings. Our algorithm costs $tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ time, while the query lower bound for the problem is $tildeOmega(n2/3/d1/6)$.
  arXiv  Detail & Related papers  (2024-10-21T15:52:08Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26: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 $\tilde{\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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• 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)
• 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)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  We study algorithms for solving the problem of constructing a text from a dictionary (sequence of small strings) The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments.
  arXiv  Detail & Related papers  (2020-05-28T22:44:01Z)

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.