製品分布の下での設定された絶頂の上限

Question

コミュニケーションの複雑さの2パーティモデルでの設定された間に問題の問題については、Aliceに入力 $ x $ 、bobが与えられ、入力 $ Y $ 、 $ x $ 、 $ y $ は< span class="math-container"> $ n $ -length bitstrings（一部の配布からサンプリングされました）。 $ [n] $ 、つまり $ x_i= 1 $ は $ i $ -thビットの $ x $ はサブセット内です。目標は、 $ x $ 、 $ y $ で表されるサブセットが答えるかどうかに応答することです。できるだけ少ないコミュニケーションを使用することによって互いに派生します。ランダム化されたプロトコルの最悪の場合には、 $ \ omega（n）$ ビットが必要です。

教科書のドラフトに出会った Anup Raoによる通信複雑さとAmir Yehudayoff 。のの $ o（n ^ {2 /）のの数で解決できるAMIR Yehudayoff 。 AliceとBobの入力が独立してサンプリングされている場合、3} \ log ^ 2 n）$ ビット。

次のプロトコルを検討してください。座標 $ j \ in [n] $ の場合、 $ H（x_j）$ $ h（y_j）$ は、少なくとも $ \ epsilon $ の両方で、aliceとbobは $ x_j、y_j $ 。それらは、そのような座標が見つからないまで、それらがこのステップを見そして繰り返す値を調整する。この時点で、AliceとBobはShannonの符号化定理を使用して $ x $ 、 $ y $ をエンコードします。 $ \ epsilon $ を設定する方法を示して、予想される通信が $ n ^ {2/3} \ logによって制限される可能性があるようにします。 ^ 2 n $ 。ヒント： $ h（x_j）\ le \ epsilon $ の事実を使用する $ pr [x_j= 1] \ GE \ OMEGA（\ epsilon /（\ log（1 /ε））$ 。

iアイデアは、 $ x $ と $ y $ が$ y $ のすべてのインデックスを最初に通信することです。大きなエントロピーとそれから、残りのインデックスが小さなエントロピーを持っている必要があるという事実を使用します。ただし、プロトコルの詳細と、 $ x $ と $ y $ の独立性が含まれています。 、私には明らかではありません。

Answer 1

アルゴリズムの最初の段階では、プレイヤーは高エントロピー座標をズームインします。それらは $ o（1）$ ビットを交換し、確率 $ \ omomega（\ epsilon ^ 2 / \ log ^ 2（1 / \ epsilon））$ （ここでは独立性を使用します）。したがって、このフェーズは、ほとんどの $ O（\ log ^ 2（1 / \ epsilon）/ \ epsilon ^ 2）$ ビットを使用しています。 2番目のフェーズは、 $ o（n \ epsilon）$ ビットを使用します。合計で、私たちはこれを期待してこの多くのビットを使いました。 $$ O（\ log ^ 2（1 / \ epsilon）/ epsilon ^ 2 + \ epsilon n）。 $$ $ \ epsilon= 1 / n ^ {1/3} $ を選択して、指定されたバインドを取得します。

独立していないので、第1段階の各ステップでの停止確率を制御することはできません。たとえば、 $ x $ がランダムに一様にサンプリングされ、 $ y $ が $ x $ の否定。この場合、最初のフェーズは停止することはなく、プロトコルは常に $ 2n $ ビットを使用します。

脇には、上限を $ o（\ sqrt {n} \ log n）$ に改善できます。これは、下限 $ \ omomega（\ sqrt {n}）$ （ギャップは文学で閉じられているかもしれません）。 講義ノートPrahladh Harsha < / a>。