論文の概要: Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings

• arxiv url: http://arxiv.org/abs/2411.02421v1
• Date: Mon, 21 Oct 2024 15:52:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 12:31:14.481138
• Title: Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings
• Title（参考訳）: 実行長符号化文字列間の最も長い共通部分列探索のための近似量子アルゴリズム
• Authors: Tzu-Ching Lee, Han-Hsuan Lin,
• Abstract要約: 2つのラン長符号化(RLE)文字列間の最長コモン(LCS)問題に対して、近似量子アルゴリズムを提案する。 我々のアルゴリズムのコストは$tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ timeであるのに対し、問題のクエリの下限は$tildeOmega(n2/3/d1/6)$である。
• 参考スコア（独自算出の注目度）: 0.8057006406834466
• License:
• Abstract: We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tilde{\Omega}(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $\Omega(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.
• Abstract（参考訳）: 2つのラン長エンコード(RLE)文字列間の最長共通サブストリング(LCS)問題に対して、ラン長のプレフィックスサムが与えられることを前提として、近似量子アルゴリズムを提案する。 我々のアルゴリズムは、$\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, and the query lower bound for the problem is $\tilde{\Omega}(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, and $d$ is the encoded length of the LCS。 我々は2つの理由からプレフィックスサムオラクルの使用を正当化する。 まず、プレフィックスサムオラクルの作成は、RLE圧縮において一定のオーバーヘッドしか発生しないことに留意する。 第二に、オラクルがなければ、この問題に対する$\mathsf{PARITY}$の削減により、2つのRLE文字列が与えられた LCS を見つけるという量子クエリの複雑さに、$\Omega(n/\log^2n)$低い境界があることが示される。 また,小さな修正を加えて,RLE文字列に対する最長繰り返しのサブストリング問題を解く。

関連論文リスト

• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings [0.951828574518325]
  ラン長符号化(RLE)入力に対して,最長共通(LCS)問題に対するサブ線形量子アルゴリズムを提案する。 我々のアルゴリズムは$tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ timeで、$n$と$tilden$はそれぞれ入力のエンコードされた長さとデコードされた長さである。
  論文  参考訳（メタデータ） (2023-10-02T08:14:34Z)
• Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
  LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。 計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-03T19:27:57Z)
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems [11.048346250166073]
  テキスト集合問題の2つのバージョンについて考察する。 文字列のシーケンスは$s1,dots,sn$ of total length $L$ that is a dictionary, string $t$ of length $m$ that is textsです。 どちらの問題に対しても、従来の量子アルゴリズムよりもうまく動作する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-18T14:16:49Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
  ほぼ最適なクエリ複雑度と時間複雑度を持つ基本文字列問題に対する量子アルゴリズムを提案する。 これらの問題には、Longest Common Substring、Lexicographically Minimal String Rotation、Longest Square Substringが含まれる。 我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
  論文  参考訳（メタデータ） (2021-10-19T02:32:18Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。 この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
  論文  参考訳（メタデータ） (2020-05-28T22:44:01Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。