改良された円形k-Mismatchスケッチ【JST・京大機械翻訳】

Golan Shay; Kociumaka Tomasz; Kopelowitz Tsvi; Porat Ely; Uznanski Przemyslaw

プレプリント

J-GLOBAL ID：202202216255454240 整理番号：22P0163280

改良された円形k-Mismatchスケッチ【JST・京大機械翻訳】

Improved Circular $k$-Mismatch Sketches

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2020年06月24日プレプリントサーバーでの情報更新日： 2020年06月24日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

同じ長さの2つのストリングS_1とS_2の間のシフト距離sh(S_1,S_2)は,S_1とS_2の回転(循環シフト)の間の最小Hamming距離として定義される。シフト距離をスケッチする問題,すなわち,2つのスケッチの受信において,スケッチ(要約)sk(S_1)とsk(S_2)を独立に計算する2つの同一プレーヤ(エンコーダ)に,長さnのストライシングS_1とS_2を与え,そして,2つのスケッチを受信するとき,第3プレーヤー(デコーダ)は,高い確率で(または近似)sh(S_1,S_2)を計算することができる。本論文は,主に,復号器がすべての関係者に知られているパラメータであるsh(S_1,S_2)>kのとき,復号器が故障を宣言できる問題のより一般的なk-ミスマッチバージョンに焦点を合わせる。また,D(n)がnのディバイザの数である,サイズO(k+D(n))の正確な円形k-不整合スケッチを導入した。また,そのスケッチサイズは線形ホモモルフィックスケッチのクラスにおいて最適であることを示した。著者らは,サイズO(k)の(非線形)正確な円形k-ミスマッチスケッチを設計することによって,この下限を避けた。このサイズは通信-複雑性下限と整合する。また,CrouchとMcGregor(APPROX′11)のO(ε ̄-2√n)サイズスケッチで改善するサイズO(min(ε ̄-2√k,ε ̄-15√n))の(1±ε)近似円形k-ミスマッチスケッチを設計した。【JST・京大機械翻訳】

, , , , , , ,
, , 【Automatic Indexing@JST】

符号理論 , 光通信方式・機器 , データ保護

前のページに戻る