Fugu-MT 論文翻訳(概要): A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

論文の概要: 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}$。

関連論文リスト

Quantum Algorithm for the Multiple String Matching Problem [0.0]
我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-22T10:50:43Z)
Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings [0.8057006406834466]
2つのラン長符号化(RLE)文字列間の最長コモン(LCS)問題に対して、近似量子アルゴリズムを提案する。我々のアルゴリズムのコストは$tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ timeであるのに対し、問題のクエリの下限は$tildeOmega(n2/3/d1/6)$である。
論文参考訳（メタデータ） (2024-10-21T15:52:08Z)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
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)
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)
Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文参考訳（メタデータ） (2020-05-28T22:44:01Z)

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