論文の概要: On the Communication Complexity of Approximate Pattern Matching

• arxiv url: http://arxiv.org/abs/2403.18812v2
• Date: Wed, 09 Oct 2024 12:08:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-10 14:26:20.308010
• Title: On the Communication Complexity of Approximate Pattern Matching
• Title（参考訳）: 近似パターンマッチングの通信複雑性について
• Authors: Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz,
• Abstract要約: 上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。 また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
• 参考スコア（独自算出の注目度）: 2.4167127333650202
• License:
• Abstract: The decades-old Pattern Matching with Edits problem, given a length-$n$ string $T$ (the text), a length-$m$ string $P$ (the pattern), and a positive integer $k$ (the threshold), asks to list all fragments of $T$ that are at edit distance at most $k$ from $P$. The one-way communication complexity of this problem is the minimum amount of space needed to encode the answer so that it can be retrieved without accessing the input strings $P$ and $T$. The closely related Pattern Matching with Mismatches problem (defined in terms of the Hamming distance instead of the edit distance) is already well understood from the communication complexity perspective: Clifford, Kociumaka, and Porat [SODA 2019] proved that $\Omega(n/m \cdot k \log(m/k))$ bits are necessary and $O(n/m \cdot k\log (m|\Sigma|/k))$ bits are sufficient; the upper bound allows encoding not only the occurrences of $P$ in $T$ with at most $k$ mismatches but also the substitutions needed to make each $k$-mismatch occurrence exact. Despite recent improvements in the running time [Charalampopoulos, Kociumaka, and Wellnitz; FOCS 2020 and 2022], the communication complexity of Pattern Matching with Edits remained unexplored, with a lower bound of $\Omega(n/m \cdot k\log(m/k))$ bits and an upper bound of $O(n/m \cdot k^3\log m)$ bits stemming from previous research. In this work, we prove an upper bound of $O(n/m \cdot k \log^2 m)$ bits, thus establishing the optimal communication complexity up to logarithmic factors. We also show that $O(n/m \cdot k \log m \log (m|\Sigma|))$ bits allow encoding, for each $k$-error occurrence of $P$ in $T$, the shortest sequence of edits needed to make the occurrence exact. We leverage the techniques behind our new result on the communication complexity to obtain quantum algorithms for Pattern Matching with Edits.
• Abstract（参考訳）: 数十年前のPattern Matching with Edits問題では、long-n$ string $T$ (テキスト)、 length-m$ string $P$ (パターン)、 positive integer $k$ (しきい値)が与えられた。 この問題の一方的な通信の複雑さは、入力文字列の$P$と$T$にアクセスすることなく、答えをエンコードするために必要な最小の空間量である。 Clifford, Kociumaka, Porat [SODA 2019] は$\Omega(n/m \cdot k \log(m/k))$ bits が必須であり、$O(n/m \cdot k\log (m|\Sigma|/k))$ bits が十分であることを示した。 近年のランニングタイムの改善 (Charalampopoulos, Kociumaka, Wellnitz, FOCS 2020, 2022) にもかかわらず、編集とのパターンマッチングの通信の複雑さは未探索のままであり、その下限は$\Omega(n/m \cdot k\log(m/k))$ bits、上限は$O(n/m \cdot k^3\log m)$ bitsであった。 本研究では,$O(n/m \cdot k \log^2m)$ビットの上限を証明し,対数的因子まで最適な通信複雑性を確立する。 また、$O(n/m \cdot k \log m \log (m|\Sigma|))$ bits は、$k$-error の発生毎に$P$ in $T$ のエンコードを可能にする。 我々は、新しい結果の裏にある技術を活用して、パターンマッチングと編集のための量子アルゴリズムを得る。

関連論文リスト

• Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
  パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。 時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
  論文  参考訳（メタデータ） (2024-10-09T12:05:26Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
  論文  参考訳（メタデータ） (2024-05-08T02:17:10Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
  論文  参考訳（メタデータ） (2023-11-03T09:09:23Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50: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)
• The quantum query complexity of composition with a relation [78.55044112903148]
  Belovs は負の重み付け逆法の修正版 $mathrmADV_relpm(f)$ を与えた。 関係が効率よく検証できる:$mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$。
  論文  参考訳（メタデータ） (2020-04-14T12:07:20Z)
• 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)

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

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