反濃縮と正確なギャップハミング問題【JST・京大機械翻訳】

Rao Anup; Yehudayoff Amir

プレプリント

J-GLOBAL ID：202202216238344350 整理番号：22P0023611

反濃縮と正確なギャップハミング問題【JST・京大機械翻訳】

Anti-concentration and the Exact Gap-Hamming Problem

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

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

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

2つの独立したランダムベクトルの内積に対する抗濃度限界を証明し,これらの限界を用いて通信複雑度における下限を証明した。著者らは,もしA,Bが|A|||B||2 ̄1.01nを有する立方体{±1} ̄nの部分集合であり,X∈AとY∈Bが独立に,そして一様にサンプリングされ,次に,内積・X,Y〉が,大部分のO(1/√n)で確率で任意の固定値を取ることを示した。事実,以下の強い「平滑性」ステートメント:max_k|Pr[||X,Y〉=k]-Pr[・X,Y〉=k+4]||O(1/n)を証明した。これらの結果を用いて,正確なギャップ-ハミング問題は線形通信を必要とし,通信複雑度における未解決問題を解決することを証明した。また,低いエントロピーを持つ構造化分布に対する抗濃縮を結論づけた。x∈Z ̄nがゼロ座標を有しないならば,B⊆{±1} ̄nは,次元0.51nのF_2 ̄nの部分空間に対応し,次に,max_kPr[ε_x,Y〉=k]≦O(√ln(n)/n)であった。【JST・京大機械翻訳】

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

半導体結晶の電子構造 , 符号理論 , 数値計算

, ,

前のページに戻る