論文の概要: Can You Solve Closest String Faster than Exhaustive Search?
- arxiv url: http://arxiv.org/abs/2305.16878v1
- Date: Fri, 26 May 2023 12:30:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 15:03:17.269559
- Title: Can You Solve Closest String Faster than Exhaustive Search?
- Title（参考訳）: クローズド文字列は排他的検索より早く解けるか?
- Authors: Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., and Ron
Safier
- Abstract要約: 与えられた集合を表すのに最適な文字列を見つけるという根本的な問題を研究する。
本稿では,最も近い文字列問題は,自明な網羅的探索アルゴリズムよりも高速なアルゴリズムを許容するかどうかを考察する。
- 参考スコア（独自算出の注目度）: 4.963483138661772
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the fundamental problem of finding the best string to represent a
given set, in the form of the Closest String problem: Given a set $X \subseteq
\Sigma^d$ of $n$ strings, find the string $x^*$ minimizing the radius of the
smallest Hamming ball around $x^*$ that encloses all the strings in $X$. In
this paper, we investigate whether the Closest String problem admits algorithms
that are faster than the trivial exhaustive search algorithm. We obtain the
following results for the two natural versions of the problem:
$\bullet$ In the continuous Closest String problem, the goal is to find the
solution string $x^*$ anywhere in $\Sigma^d$. For binary strings, the
exhaustive search algorithm runs in time $O(2^d poly(nd))$ and we prove that it
cannot be improved to time $O(2^{(1-\epsilon) d} poly(nd))$, for any $\epsilon
> 0$, unless the Strong Exponential Time Hypothesis fails.
$\bullet$ In the discrete Closest String problem, $x^*$ is required to be in
the input set $X$. While this problem is clearly in polynomial time, its
fine-grained complexity has been pinpointed to be quadratic time $n^{2 \pm
o(1)}$ whenever the dimension is $\omega(\log n) < d < n^{o(1)}$. We complement
this known hardness result with new algorithms, proving essentially that
whenever $d$ falls out of this hard range, the discrete Closest String problem
can be solved faster than exhaustive search. In the small-$d$ regime, our
algorithm is based on a novel application of the inclusion-exclusion principle.
Interestingly, all of our results apply (and some are even stronger) to the
natural dual of the Closest String problem, called the \emph{Remotest String}
problem, where the task is to find a string maximizing the Hamming distance to
all the strings in $X$.
- Abstract（参考訳）: x \subseteq \sigma^d$ of $n$ string が与えられたとき、最小のハミングボールの半径を最小化する$x^*$ を、$x$ で囲む$x^*$ で求める。
本稿では,最も近い文字列問題は,自明な探索アルゴリズムよりも高速なアルゴリズムを許容するかどうかを検討する。
問題の2つの自然なバージョンについて以下の結果が得られる: $\bullet$ 連続的最も近い文字列問題において、目標は$\sigma^d$ で解文字列 $x^*$ を見つけることである。
二進文字列の場合、全探索アルゴリズムは時間$O(2^d poly(nd))$で実行され、強い指数時間仮説が失敗しない限り、任意の$\epsilon > 0$に対して、時間$O(2(1-\epsilon) d} poly(nd))$で改善できないことが証明される。
$\bullet$ 離散クローズスト文字列問題では、$x^*$ は入力セット $X$ にある必要がある。
この問題は多項式時間で明らかであるが、そのきめ細かい複雑さは、次元が $\omega(\log n) < d < n^{o(1)}$ であるとき、二次時間 $n^{2 \pm o(1)}$ と特定されている。
この既知の難易度を新しいアルゴリズムで補完し、基本的に$d$がハードレンジから外れると、離散的最寄り文字列問題は徹底的な探索よりも早く解くことができることを証明します。
我々のアルゴリズムは、小額のd$レジームにおいて、包含-排他原理の新たな応用に基づいている。
興味深いことに、我々の結果のすべては、最も近い文字列問題の自然双対問題、すなわち \emph{remotest string}問題に適用され、ここでは、すべての文字列に対するハミング距離を最大化する文字列を$x$で見つけることがタスクである。
関連論文リスト
- 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) - 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) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。