l_∞保証による線形ハッシングと両側Kakeya限界【JST機械翻訳】

Dhar Manik; Dvir Zeev

プレプリント

J-GLOBAL ID：202202219241000954 整理番号：22P0325162

l_∞保証による線形ハッシングと両側Kakeya限界【JST機械翻訳】

Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

有限体上のランダムに選んだ線形写像はl_∞の意味でよいハッシュ関数を与えることを示す。より具体的には,集合S⊂F_q ̄nとランダム選択線形写像L:F_q ̄n→F_q ̄tを考慮し,q ̄tは|S|より十分小さいとした。U_SをS上に一様に分布する確率変数と表示する。筆者らの主定理は,Lの選択に対する高い確率で,確率変数L(U_S)がl_∞ノルムにおいて一様に近いことを示した。言い換えれば,範囲F_q ̄tの全ての元素は,それにマップされたSの中のほぼ同じ数の元素を持つ。これは,統計的あるいはl_1,距離(関数のより豊富なクラスに対して)の下でのアナログステートメント,ならびに線形ハッシュ関数における期待される最大’バケツサイズに関する先行研究を証明する広く用いられているLeftover Hash Lemma(LHL)を補完した。負荷均衡文献[RS98]からの既知の限界により,著者らの結果はタイトであり,線形関数はエントロピー損失における一定因子までの厳密なランダム関数と同様にハッシュであることを示した。この証明は,線形ハッシングと有限体Kakeya問題間の関係を利用し,この分野で開発されたツールのいくつか,特に多項式法を拡張した。【JST機械翻訳】

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

符号理論 , 信号理論 , 通信方式一般

, , ,

前のページに戻る