三角形フリーグラフの下限

私はそれが言うところのメモのセットを読んでいた

無作為化さえしても$ n $ nodesを持つ(重み付けされていない無向グラフ)$ G
$に三角形が含まれているかどうかを判断するには、ワンパスアルゴリズムに$ Omega(n ^
2)$スペースが必要であることがわかる。

私はdisjointnessのための無作為化されたプロトコルが$
Omega(n)$スペースを必要とするような通信の複雑さの結果を見ましたが、上の結果のスケッチまたは参照は何ですか?

ベストアンサー

まず、問題$ C $に対して空間$ s(n)$で動作するストリーミングアルゴリズムは、$ s(n)$ビットの通信を使用して$ C
$の通信プロトコルを意味します。入力$ x $のアリスはストリーミングを実行しますアルゴリズムを$ x
$で実行し、ストリームの最後にあるマシンの構成をBob($ s(n)$ bits)に渡し、$ y
$を入力したBobが提供されたアルゴリズムからストリーミングアルゴリズムを実行します設定し、結果を返します。したがって、通信下限はストリーミング下限を意味する。

次に、INDEXと呼ばれる次の問題を考えてみましょう。アリスは$ n $ビット文字列$ x $を取得し、ボブは整数$ i
in [n] $を取得し、$ i $ thビットの値を決定します。 $ x $、$ x_i
$。情報統計の引数を使って証明できる次の結果を引用します。

Claim 1: Any randomized (1/3-error, say)
protocol for INDEX requires $Omega(n)$ communication.

これで、INDEXから三角形の問題にまで減らすことができます。特に、INDEXの与えられたインスタンス$(x、i)$は$ V =
L cup R cup {s } $より$ E_A $と$ E_B $を設定できます。$ L = {y_1 $ {$
sqrt {n}} } $ {$ sqrt {n}} } $ {$ sqrt { $ X_i = 1 $ならば、結果のグラフ$ G
$は三角形でないという性質を持つ sqrt {n} + 1 = O( sqrt {n})$ nodes)さらに、アリスは$ E_A
$自身を計算し、ボブは$ E_B $自身を計算することができます。これを行うには、いくつかのペアリング関数$ p:[n] を[
sqrt {n}] times [ sqrt {n}] $を選択し、$ p_L(k)$が、 $ p(k)$と$
p_R(k​​)$は秒です。これを使用して、ビット位置をエッジにマッピングします。次に、$ E_A = {(y_
{p_L(k)}、z_ {p_R(k​​)}) | x_k = 1 }
$とする。これは二部グラフであることに注意してください。 $ E_B = {(s、y_ {p_L(i)})、(s、z_
{p_R(i)})} $とする。 $ E_A $は三角形を持たず、$ E_A $は三角形を形成します。$ y_ {p_L(i)}
$と$ z_ {p_R(i)} $の間のエッジは$ x_i = 1 $。

グラフが三角形でないかどうかを判定するための$ o(n ^ 2)$通信プロトコルは、INDEX下限と容易に矛盾します。アリスは$
x $を取得し、ボブは$ i $を取得します。アリスとボブは、コミュニケーションなしでそれぞれ$ E_A $と$ E_B
$を計算します。彼らは$ o( sqrt {n} ^ 2)=
o(n)$通信を使って、サブルーチンとして三角形のないプロトコルを使います。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です