論文の概要: A sublinear time quantum algorithm for longest common substring problem
between run-length encoded strings
- arxiv url: http://arxiv.org/abs/2310.00966v1
- Date: Mon, 2 Oct 2023 08:14:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-04 23:04:07.526473
- Title: A sublinear time quantum algorithm for longest common substring problem
between run-length encoded strings
- Title(参考訳): ラン長符号化文字列間の最長共通部分弦問題に対する線形時間量子アルゴリズム
- Authors: Tzu-Ching Lee and Han-Hsuan Lin
- Abstract要約: ラン長符号化(RLE)入力に対して,最長共通(LCS)問題に対するサブ線形量子アルゴリズムを提案する。
我々のアルゴリズムは$tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ timeで、$n$と$tilden$はそれぞれ入力のエンコードされた長さとデコードされた長さである。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): ラン長エンコードされた(RLE)入力に対して、ランのプレフィックスサムが与えられると仮定して、最長共通サブストリング(LCS)問題に対するサブ線形量子アルゴリズムを提案する。
我々のアルゴリズムは、$\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$ time で、$n$ と $\tilde{n}$ はそれぞれ入力の符号化長と復号長である。
オーラクルがなければ、この問題に対して$\Omega(n/\log^2n)$ lower-bound on the quantum query complexity of find LCS given two RLE strings due by the reduction of $\mathsf{PARITY}$。
関連論文リスト
- 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) - 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳(メタデータ) (2021-03-03T22:42:15Z) - Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms
for String Problems [5.490993287665715]
最も長いコモン(LCS)、長いパリンドローム(LPS)、そしてウルム距離(UL)は、古典的に線形に近い時間で解くことができる3つの基本弦問題である。
これらの問題に対する線形時間量子アルゴリズムと量子下界について述べる。
論文 参考訳(メタデータ) (2020-10-23T01:00:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。