論文の概要: Approximate Trace Reconstruction

• arxiv url: http://arxiv.org/abs/2012.06713v2
• Date: Wed, 16 Dec 2020 18:27:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-10 05:09:36.076278
• Title: Approximate Trace Reconstruction
• Title（参考訳）: 近似トレース再構成
• Authors: Sami Davies, Miklos Z. Racz, Cyrus Rashtchian, Benjamin G. Schiffer
• Abstract要約: 我々は、およその再建のリラックスした問題を検討する。 ここでの目標は、編集距離で元の文字列に近い文字列を出力することである。 特定のクラスに属する文字列を概ね再構成できるアルゴリズムをいくつか提示する。
• 参考スコア（独自算出の注目度）: 4.521119623956821
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the usual trace reconstruction problem, the goal is to exactly reconstruct an unknown string of length $n$ after it passes through a deletion channel many times independently, producing a set of traces (i.e., random subsequences of the string). We consider the relaxed problem of approximate reconstruction. Here, the goal is to output a string that is close to the original one in edit distance while using much fewer traces than is needed for exact reconstruction. We present several algorithms that can approximately reconstruct strings that belong to certain classes, where the estimate is within $n/\mathrm{polylog}(n)$ edit distance, and where we only use $\mathrm{polylog}(n)$ traces (or sometimes just a single trace). These classes contain strings that require a linear number of traces for exact reconstruction and which are quite different from a typical random string. From a technical point of view, our algorithms approximately reconstruct consecutive substrings of the unknown string by aligning dense regions of traces and using a run of a suitable length to approximate each region. To complement our algorithms, we present a general black-box lower bound for approximate reconstruction, building on a lower bound for distinguishing between two candidate input strings in the worst case. In particular, this shows that approximating to within $n^{1/3 - \delta}$ edit distance requires $n^{1 + 3\delta/2}/\mathrm{polylog}(n)$ traces for $0< \delta < 1/3$ in the worst case.
• Abstract（参考訳）: 通常のトレース再構成問題では、未知の長さの文字列を、独立に何度も削除チャネルを通過した後、正確に再構築し、一連のトレース(すなわち、文字列のランダムな部分列)を生成する。 近似復元の緩和問題を考察する。 ここでの目標は、正確な再構築に必要なトレースよりも少ないトレースを使用して、編集距離で元の文字列に近い文字列を出力することである。 推定値が$n/\mathrm{polylog}(n)$Edit distance内にあり、$\mathrm{polylog}(n)$ traces(あるいは単に1つのトレース)しか使用できないような、あるクラスに属する文字列をおよそ再構成できるアルゴリズムをいくつか提示する。 これらのクラスは、正確な復元のために線形数のトレースを必要とする文字列を含み、典型的なランダム文字列とは全く異なる。 技術的観点から,我々のアルゴリズムは,トレースの高密度領域を整列させ,各領域を近似するために適切な長さのランを用いて,未知文字列の連続的なサブストリングを概ね再構成する。 アルゴリズムを補完するために、近似再構成のための一般的なブラックボックスの下限を示し、最悪の場合、2つの入力文字列を区別するために下限の上に構築する。 特に、これは$n^{1/3 - \delta}$編集距離が$n^{1 + 3\delta/2}/\mathrm{polylog}(n)$ traces for $0< \delta < 1/3$ であることを示している。

関連論文リスト

• 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)
• Profile Reconstruction from Private Sketches [13.929335175122265]
  $mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。 分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。 LPベースの手法の高速化方法を示します
  論文  参考訳（メタデータ） (2024-06-03T09:51:28Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。 この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
  論文  参考訳（メタデータ） (2020-05-28T22:44:01Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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