コミュニケーションの複雑さ

理論計算機科学において、通信複雑性は、問題への入力が2 つ以上の当事者間で分散されている場合に、問題を解決するために必要な通信量を研究します。通信複雑性の研究は、1979 年にAndrew Yaoが、複数のマシン間で計算を分散する問題を研究しているときに初めて導入されました。^[1] この問題は通常、次のように表現されます。2 つの当事者 (従来はAlice と Bobと呼ばれます) がそれぞれ (潜在的に異なる) -ビット文字列とを受け取ります。目標は、Alice が、両者間の通信量を最小限に抑えながら、およびに依存する特定の関数 の値を計算することです。 ${\displaystyle n}$${\displaystyle x}$${\displaystyle y}$${\displaystyle f(x,y)}$${\displaystyle x}$${\displaystyle y}$

アリスとボブは、ボブが ビットの文字列全体をアリスに送信することで常に成功しますが(アリスは関数を計算します)、ここでの考え方は、ビット未満の通信で計算する巧妙な方法を見つけることです。計算複雑性理論とは異なり、通信複雑性は、アリスまたはボブが実行する計算量や、使用されるメモリのサイズとは関係ありません。これは、通常、アリスまたはボブの計算能力については何も想定していないためです。 ${\displaystyle n}$ ${\displaystyle f}$${\displaystyle f}$${\displaystyle n}$

2 者間通信の複雑さと呼ばれるこの抽象的な問題、および3 者以上での一般的な形式は、多くの状況に関連しています。たとえば、 VLSI回路設計では、分散計算中にさまざまなコンポーネント間で渡される電気信号の量を減らすことで、使用されるエネルギーを最小限に抑えることが求められます。この問題は、データ構造の研究やコンピュータ ネットワークの最適化にも関連しています。この分野の概説については、Rao & Yehudayoff (2020) および Kushilevitz & Nisan (2006) の教科書を参照してください。

とします。ここで、典型的なケースでは、および と仮定します。アリスは- ビットの文字列 を保持し、ボブは- ビットの 文字列 を保持します。アリスとボブは、一度に1ビットずつ通信することにより (事前に合意された通信プロトコルを採用)、通信の最後に少なくとも 1 人が値を知っているように の値を計算したいと考えています。この時点で、答えは、1 ビット余分にかかるコストで両方の当事者が答えを知ることができるように通信し返すことができます。 を計算するこの通信問題の最悪の場合の通信複雑度は、 と表され、次のように定義されます。 ${\displaystyle f:X\times Y\rightarrow Z}$${\displaystyle X=Y=\{0,1\}^{n}}$${\displaystyle Z=\{0,1\}}$${\displaystyle n}$${\displaystyle x\in X}$${\displaystyle n}$${\displaystyle y\in Y}$${\displaystyle f(x,y)}$${\displaystyle f}$${\displaystyle D(f)}$

${\displaystyle D(f)=}$最悪の場合にアリスとボブの間で交換されるビットの最小数。

上で述べたように、任意の関数 に対して、 が成り立ちます。上記の定義を使用すると、関数 を、行がでインデックス付けされ、列が でインデックス付けされる行列(入力行列または通信行列と呼ばれる) と考えると便利です。行列のエントリは です。最初は、アリスとボブの両方が行列全体のコピーを持っています(関数が両者に知られていると仮定)。次に、関数値を計算する問題は、対応する行列エントリへの「ゼロイン」と言い換えることができます。この問題は、アリスまたはボブのどちらかがと の両方を知っていれば解決できます。通信の開始時に、入力の関数の値の選択肢の数は、行列のサイズ、つまり です。次に、各当事者が相手にビットを通信するにつれて、行/列のセットが削除され、 のサブ行列になるため、答えの選択肢の数が減ります。 ${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle D(f)\leq n}$${\displaystyle f}$ ${\displaystyle A}$${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle A_{x,y}=f(x,y)}$${\displaystyle A}$${\displaystyle f}$${\displaystyle x}$${\displaystyle y}$${\displaystyle 2^{2n}}$${\displaystyle A}$

より正式には、集合は、かつ のときはいつでも、であるとき、 （組み合わせ的）長方形と呼ばれます。同様に、 が、ある かつ に対してと表せるとき、 は組み合わせ的長方形です。ビットがすでに当事者間で交換されている場合を考えてみましょう。ここで、特定の に対して、行列を定義しましょう。 ${\displaystyle R\subseteq X\times Y}$${\displaystyle (x_{1},y_{1})\in R}$${\displaystyle (x_{2},y_{2})\in R}$${\displaystyle (x_{1},y_{2})\in R}$${\displaystyle R}$${\displaystyle R=M\times N}$${\displaystyle M\subseteq X}$${\displaystyle N\subseteq Y}$${\displaystyle k}$${\displaystyle h\in \{0,1\}^{k}}$

${\displaystyle T_{h}=\{(x,y):{\text{ 入力 }}(x,y){\text{ で交換される }}k{\text{-ビットは }}h\}}$

すると、 となり、 が内の組合せ長方形であることを示すのは難しくありません。 ${\displaystyle T_{h}\subseteq X\times Y}$${\displaystyle T_{h}}$${\displaystyle A}$

アリスとボブが入力文字列が等しいかどうかを判断しようとするケースを考えます。 正式には、の場合に と表記される等値関数を で定義します。 以下に示すように、決定論的通信プロトコルを解決するには、最悪の場合でも ビットの通信が必要になります。 ウォームアップの例として、 の単純なケースを考えます。 この場合の等値関数は、以下の行列で表すことができます。 行は のすべての可能性を表し、 の列は のすべての可能性を表します。 ${\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle EQ(x,y)=1}$${\displaystyle x=y}$${\displaystyle EQ}$${\displaystyle n}$${\displaystyle x,y\in \{0,1\}^{3}}$${\displaystyle x}$${\displaystyle y}$

この表では、関数は が等しい場合（つまり、対角線上にある場合）にのみ 1 と評価されます。また、1 ビットの通信によって、誰かの可能性が半分に分割されることも簡単にわかります。 の最初のビットが 1 の場合、列の半分だけを検討します（ は100、101、110、または 111 に等しい場合があります）。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle y}$

証明。 と仮定します。これは、 とが同じ通信トランスクリプト を持つが存在することを意味します。このトランスクリプトは長方形を定義するため、も 1 である必要があります。定義と により、の場合にのみ等式が成り立つことが分かっています。これにより矛盾が生じます。 ${\displaystyle D(EQ)\leq n-1}$${\displaystyle x\neq x'}$${\displaystyle (x,x)}$${\displaystyle (x',x')}$${\displaystyle h}$${\displaystyle f(x,x')}$${\displaystyle x\neq x'}$${\displaystyle (a,b)}$${\displaystyle a=b}$

決定論的通信の下限を証明するこの手法は、フーリングセット手法と呼ばれます。^[2]

上記の定義では、 2 つの当事者間で決定論的に送信されなければならないビットの数について検討しています。両方の当事者が乱数ジェネレーターにアクセスできる場合、交換される情報が大幅に少なくなるため、 の値を決定できるでしょうか? Yao は、彼の独創的な論文^[1]で、 ランダム化された通信の複雑さを定義することでこの質問に答えています。 ${\displaystyle f}$

関数のランダム化プロトコルには両側エラーがあります。 ${\displaystyle R}$${\displaystyle f}$

${\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0}$

${\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1}$

ランダム化プロトコルは、通常の入力に加えて追加のランダム文字列を使用する決定論的プロトコルです。これには 2 つのモデルがあります。公開文字列は、両方の当事者が事前に知っているランダム文字列ですが、プライベート文字列は、一方の当事者によって生成され、もう一方の当事者に伝達される必要があります。以下に示す定理は、任意の公開文字列プロトコルは、元のプロトコルと比較してO(log n)の追加ビットを使用するプライベート文字列プロトコルによってシミュレートできることを示しています。

上記の確率不等式では、プロトコルの結果はランダム文字列のみに依存すると理解されていることに注意してください。文字列xとy は両方とも固定されたままです。言い換えると、ランダム文字列r を使用しているときにR ( x、y ) がg ( x、y、r ) を生成する場合、文字列rのすべての選択肢の少なくとも 2/3 に対してg ( x、y、r ) = f ( x、y ) となります。

ランダム化された複雑さは、そのようなプロトコルで交換されるビット数として単純に定義されます。

片側誤差を持つランダム化プロトコルを定義することも可能であり、複雑さも同様に定義されることに注意してください。

前のEQの例に戻ると、確実性が必要ない場合、アリスとボブは⁠ ⁠${\displaystyle O(\log n)}$メッセージのみを使用して同等性を確認できます。次のプロトコルを検討してください。アリスとボブの両方が同じランダム文字列 にアクセスできると仮定します。アリスはこのビット ( bと呼びます) を計算してボブに送信します。 ( はGF(2)のドット積です。) 次にボブはbを と比較します。それらが同じ場合、ボブはx がyに等しいと言って受け入れます。そうでない場合、ボブは拒否します。 ${\displaystyle z\in \{0,1\}^{n}}$${\displaystyle z\cdot x}$${\displaystyle (\cdot )}$${\displaystyle z\cdot y}$

明らかに、であればなので です。x がyと等しくない場合でもとなる可能性があり、ボブに間違った答えを与えることになります。 なぜこのようなことが起こるのでしょうか? ${\displaystyle x=y}$${\displaystyle z\cdot x=z\cdot y}$${\displaystyle Prob_{z}[Accept]=1}$${\displaystyle z\cdot x=z\cdot y}$

xとyが等しくない 場合は、いくつかの場所で異なる必要があります。

${\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}$

xとy が一致する場合、これらの項はドット積に等しく影響します。これらの項を無視して、xとy が異なる部分だけを見ても問題ありません。さらに、ドット積が等しいかどうかを変えずにビットを交換できます。つまり、x にゼロのみが含まれ、y に1 のみが含まれたビットを交換できるということです。 ${\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}$${\displaystyle x_{i}}$${\displaystyle y_{i}}$

${\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}$

と に注意してください。ここでの疑問は、ランダムな文字列 に対して となる確率はいくらかということです。それぞれがとなる確率は等しいので、${\displaystyle z'\cdot x'=0}$${\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}$${\displaystyle z'}$${\displaystyle \Sigma _{i}z'_{i}=0}$${\displaystyle z'_{i}}$0または1 の場合、この確率はちょうど です。したがって、x がyと等しくない場合は、 です。アルゴリズムは何度も繰り返すことで精度を高めることができます。これは、ランダム化通信アルゴリズムの要件に適合しています。 ${\displaystyle 1/2}$${\displaystyle Prob_{z}[Accept]=1/2}$

これは、アリスとボブが長さ n のランダムな文字列を共有する場合、お互いに 1 ビットを送信して を計算できることを示しています。次のセクションでは、アリスとボブが長さnのランダムな文字列を共有するのと同じくらい良い⁠ ⁠ビットのみを交換できることが示されます。これが示されると、EQ は⁠ ⁠メッセージ で計算できることがわかります。${\displaystyle EQ(x,y)}$${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$

ランダム化された通信の複雑さのもう 1 つの例として、ギャップ ハミング問題(略してGH ) と呼ばれる例を取り上げます。形式的には、アリスとボブはどちらもバイナリ メッセージを保持しており、文字列が非常に似ているか、あまり似ていないかを判断したいと考えています。特に、次の部分ブール関数を計算するために、できるだけ少ないビットの送信を必要とする通信プロトコルを見つけたいと考えています。 ${\displaystyle x,y\in \{-1,+1\}^{n}}$

${\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}$

明らかに、プロトコルが決定論的であるためには、すべてのビットを通信する必要があります (これは、アリスとボブが互いに中継するインデックスの決定論的で厳密なサブセットがある場合、そのセット上で位置が一致しない文字列のペアがあると想像してください。中継されない位置で別の不一致が発生すると、 の結果に影響し、誤った手順が発生します)。 ${\displaystyle {\sqrt {n}}-1}$${\displaystyle {\text{GH}}_{n}(x,y)}$

すると当然の疑問が湧いてきます。もし（から一様にランダムに抽出されたランダムなインスタンスに対して）時間の誤差が許されるのであれば、より少ないビット数のプロトコルで済むのでしょうか？ 2012 年の Chakrabarti と Regev の結果により、その答えは意外にも「いいえ」であることがわかりました。彼らは、ランダムなインスタンスに対して、少なくとも時間の誤差が正しい手順は、通信に相当するビット、つまり基本的にすべてのビットを送信する必要があることを示しています。 ${\displaystyle 1/3}$${\displaystyle x,y}$${\displaystyle \{-1,+1\}^{n}}$${\displaystyle 2/3}$${\displaystyle \Omega (n)}$

両者が同じランダム文字列にアクセスできる場合、ランダム プロトコルの作成は容易になります。これは共有文字列プロトコルと呼ばれます。ただし、両者がランダム文字列を共有しない場合でも、わずかな通信コストでプライベート文字列プロトコルを使用することは可能です。任意の数のランダム文字列を使用する共有文字列ランダム プロトコルは、追加のO(log n)ビットを使用するプライベート文字列プロトコルによってシミュレートできます。

直感的に、エラーの増加がわずかでランダム プロトコルを実行するのに十分なランダム性を持つ文字列のセットを見つけることができます。このセットは事前に共有でき、ランダムな文字列を描画する代わりに、アリスとボブは共有セットからどの文字列を選択するかに同意するだけで済みます。このセットは十分に小さいため、選択を効率的に伝達できます。正式な証明は以下を参照してください。

最大エラー率が 0.1 であるランダム プロトコルP を考えます。 を長さnの番号が付けられた文字列とします。 このような が与えられた場合、いくつかをランダムに選択し、 を共有ランダム文字列として使用してPを実行する新しいプロトコルを定義します。の選択を通信するには、O (log 100 n ) = O (log  n ) ビットかかります。 ${\displaystyle R}$${\displaystyle 100n}$${\displaystyle r_{1},r_{2},\dots ,r_{100n}}$${\displaystyle R}$${\displaystyle P'_{R}}$${\displaystyle r_{i}}$${\displaystyle r_{i}}$${\displaystyle r_{i}}$

およびを、 入力 の正しい値を計算する確率として定義します。 ${\displaystyle p(x,y)}$${\displaystyle p'_{R}(x,y)}$${\displaystyle P}$${\displaystyle P'_{R}}$${\displaystyle (x,y)}$

を固定した場合、Hoeffding の不等式を使用して次の式を得ることができます。 ${\displaystyle (x,y)}$

${\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}$

したがって、固定されていない場合は、次のようになります。 ${\displaystyle (x,y)}$

${\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}$

上記の最後の等式は、異なるペアが存在するため成立します。確率は 1 ではないため、すべての に対してとなるものが存在します。 ${\displaystyle 2^{2n}}$${\displaystyle (x,y)}$${\displaystyle R_{0}}$${\displaystyle (x,y)}$

${\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}$

のエラー確率は最大で 0.1 なので、エラー確率は最大で 0.2 になります。 ${\displaystyle P}$${\displaystyle P'_{R_{0}}}$

さらに、アリスとボブが、例えばエンタングル粒子のペアなどのリソースを共有できるようにするとします。そのリソースを使用して、アリスとボブは情報を相関させ、次の意味で通信の複雑さを「縮小」 (または「単純化」) しようとします。

定義。 リソースが${\displaystyle R}$「崩壊している」と言われるのは、そのリソースを使用して、1 ビットの従来の通信だけで、アリスが任意のブール関数の最悪のシナリオの評価を知ることができる場合です。${\displaystyle R}$${\displaystyle f(x,y)}$ ${\displaystyle f}$

通信の複雑さの減少に関する驚くべき事実は、関数のエントリ サイズは任意に大きくできるものの、通信ビットの数は 1 ビットに固定されていることです。 ${\displaystyle f}$

量子相関^[3]やより一般的にはほぼ量子相関^[4]などのいくつかのリソースは非崩壊性であることが示されていますが、逆にPRボックス^[5]やいくつかの条件を満たすノイズの多いPRボックスなどの他のリソースはランダム化された通信の複雑さを崩壊させることが示されています。^{[6] [7] [8]}

ランダム化された通信の複雑さを研究する 1 つのアプローチは、分布の複雑さを介することです。

両プレイヤーの入力に関する結合分布が与えられた場合、関数の対応する分布複雑度は、入力が に従ってサンプリングされる、 となる決定論的プロトコルの最小コストです。 ${\displaystyle \mu }$${\displaystyle f}$${\displaystyle R}$${\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}$${\displaystyle \mu }$

ヤオのミニマックス原理^{[9] （}フォン・ノイマンのミニマックス定理の特殊なケース）は、関数のランダム化された通信複雑さは、その最大分布複雑さに等しく、最大値は入力のすべての結合分布（必ずしも積分布ではない！）にわたって取られることを述べています。

ヤオの原理は、関数のランダム化された通信複雑度の下限を証明するために使用できます。適切な結合分布を設計し、分布複雑度の下限を証明します。分布複雑度は決定論的プロトコルに関係するため、ランダム化されたプロトコルの下限を直接証明するよりも簡単な場合があります。

例として、分離関数 DISJ を考えてみましょう。各入力は のサブセットとして解釈され、2 つのセットが分離している場合、 DISJ( x , y )=1 になります。Razborov ^{[10] は}、次の分布を考慮して、ランダム化された通信の複雑さの下限を証明しました。確率 3/4 で、サイズ の 2 つのランダムな分離セットをサンプリングし、確率 1/4 で、一意の交差を持つサイズ の 2 つのランダムなセットをサンプリングします。 ${\displaystyle \{1,\dots ,n\}}$${\displaystyle \Omega (n)}$${\displaystyle n/4}$${\displaystyle n/4}$

分布複雑性の研究に対する強力なアプローチは情報複雑性である。Bar-Yossef、Jayram、Kumar、Sivakumar ^[11]によって始められたこのアプローチは、Barak、Braverman、Chen、Rao ^{[12]とBravermanとRao [13]}の研究で体系化された。

分布μに関する（ランダム化されている可能性のある）プロトコルRの（内部）情報複雑性は次のように定義されます。μに従ってサンプリングされたランダム入力をとし、入力に対して実行されたRのトランスクリプトをΠとします。プロトコルの情報複雑性は ${\displaystyle (X,Y)\sim \mu }$${\displaystyle X,Y}$

${\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}$

ここで、I は条件付き相互情報量を表します。最初の加数はアリスがトランスクリプトからボブの入力について知る情報量を測定し、2 番目の加数はボブがアリスの入力について知る情報量を測定しま す。

分布μに関する関数fのε誤差情報複雑度は、誤差（ μに関する）が最大でもεであるfのプロトコルの最小情報複雑度です。

Braverman と Rao は、情報は償却された通信に等しいことを証明しました。これは、 fのn 個の独立したコピーを解くコストが、fの情報複雑性のおよそn倍であることを意味します。これは、特定の情報ソースからデータを送信するために必要な償却されたビット長としてのShannon エントロピーのよく知られた解釈に類似しています。Braverman と Rao の証明では、「プロトコル圧縮」と呼ばれる手法が使用されています。この手法では、情報効率の高いプロトコルが通信効率の高いプロトコルに「圧縮」されます。

情報計算量の技術により、集合の分離性の正確な（一次までの）通信計算量を計算することが可能になる。^[14]${\displaystyle 1.4923\ldots n}$

情報複雑性技術は拡張定式化の解析にも使用されており、最大クリーク問題を近似的に解く線形計画法に基づくアルゴリズムの複雑性の本質的に最適な下限を証明しています。^[15]

オムリ・ワインスタインの2015年の調査^[16]ではこの問題について調査している。

量子通信複雑度は、分散計算中に量子効果を使用することで可能な通信削減を定量化しようとします。

通信の複雑さに関する量子一般化は少なくとも 3 つ提案されています。概要については、G. Brassard の推奨テキストを参照してください。

1 つ目は量子ビット通信モデルで、このモデルでは、光ファイバーを介して光子を交換するなど、従来の通信の代わりに量子通信を使用できます。

2 番目のモデルでは、通信は依然として古典的なビットで実行されますが、当事者はプロトコルの一部として無制限の量子もつれ状態を操作できます。当事者は、もつれ状態を測定することで、分散計算中に古典的な通信を節約できます。

3 番目のモデルは、量子ビット通信に加えて、以前に共有されたエンタングルメントへのアクセスを含み、3 つの量子モデルの中で最も研究が進んでいません。

非決定論的通信複雑度では、アリスとボブはオラクルにアクセスできます。オラクルのワードを受け取った後、両者は通信して推論します。非決定論的通信複雑度は、交換されたビット数の合計とオラクル ワードのコーディング長を超える すべてのペアの最大値になります。${\displaystyle f(x,y)}$${\displaystyle (x,y)}$

別の見方をすると、これは 0/1 行列のすべての 1 エントリを組み合わせ 1 長方形 (つまり、エントリがすべて 1 である非連続で非凸の部分行列 (Kushilevitz と Nisan または Dietzfelbinger らを参照)) で覆うことに相当します。非決定論的通信の複雑さは、行列の長方形被覆数の 2 進対数です。つまり、行列のすべての 1 エントリを、0 エントリをまったく覆わずに覆うために必要な組み合わせ 1 長方形の最小数です。

非決定論的通信複雑性は、決定論的通信複雑性の下限値を求める手段として用いられる（Dietzfelbingerら参照）が、非負行列の理論においても用いられ、非負行列の非負ランクの下限値を与える。^[17]

無制限エラー設定では、アリスとボブはプライベートコインと独自の入力 にアクセスできます。この設定では、アリスが の正しい値を1/2 より確実に大きい確率で応答すると、アリスは成功します。言い換えると、アリスの応答がの真の値とゼロ以外の相関関係にある場合、プロトコルは有効であると見なされます。 ${\displaystyle (x,y)}$${\displaystyle f(x,y)}$${\displaystyle f(x,y)}$

コインがプライベートであるという要件が不可欠であることに注意する。特に、アリスとボブの間で共有される公開ビットの数が通信の複雑さにカウントされない場合、任意の関数の計算には通信の複雑さがあると主張するのは簡単です。^[18]一方、アリスとボブが使用する公開ビットの数がプロトコルの総通信に対してカウントされる場合、両方のモデルは同等です。^[19]${\displaystyle O(1)}$

このモデルの下限は微妙ではあるが、極めて強力である。より具体的には、このクラスの問題に対するいかなる上限も、決定論的モデルやプライベートコインモデル、パブリックコインモデルの問題に対する同等の上限を直ちに意味することは明らかであるが、そのような上限は非決定論的通信モデルや量子通信モデルにも直ちに当てはまる。^[20]

フォースター^[21]は、このクラスの明示的な下限値を証明した最初の人物であり、内積の計算には少なくともビットの通信が必要であることを示したが、アロン、フランクル、レードルによる以前の結果では、ほとんどすべてのブール関数の通信複雑度はであることが証明されている。^[22]${\displaystyle \langle x,y\rangle }$${\displaystyle \Omega (n)}$${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}$${\displaystyle \Omega (n)}$

リフティングは、複雑性理論における一般的な手法であり、単純な複雑性の尺度の下限を、より困難な尺度の下限に「持ち上げる」ものです。

この技術は、通信の複雑さの文脈でラズとマッケンジー^[23]によって開拓され、彼らは最初のクエリから通信へのリフティング定理を証明し、その結果を使用して単調な NC階層を分離しました。

関数とガジェットが与えられた場合、それらの構成は次のように定義されます。 ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$${\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}$${\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}$

${\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}$

言い換えると、は長さ のブロックに分割され、 は長さ のブロックに分割されます。ガジェットはブロックに 回適用され、出力は に入力されます。図式的には次のよう になります。${\displaystyle x}$${\displaystyle n}$${\displaystyle a}$${\displaystyle y}$${\displaystyle n}$${\displaystyle b}$${\displaystyle n}$${\displaystyle f}$

この図では、各入力はaビットの長さで、各入力はbビットの長さです。 ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}$

の深さ の決定木は、コストが である通信プロトコルに変換できます。つまり、木がビットを照会するたびに、 の対応する値が の最適なプロトコルを使用して計算されます。Raz と McKenzie は、 がいわゆる「インデックス ガジェット」であるとき、定数係数 までこれが最適であることを示しました。この場合、は長さ(十分に大きい定数cの場合)、は長さ、 はの - 番目のビットです。 ${\displaystyle \Delta }$${\displaystyle f}$${\displaystyle \Delta \cdot D(g)}$${\displaystyle g}$${\displaystyle g}$${\displaystyle g}$${\displaystyle x}$${\displaystyle c\log n}$${\displaystyle y}$${\displaystyle n^{c}}$${\displaystyle g(x,y)}$${\displaystyle x}$${\displaystyle y}$

Raz-McKenzie の持ち上げ定理の証明では、合成関数のプロトコルを使用して の決定木を生成するシミュレーション法が使用されています。 Göös、Pitassi、Watson ^{[24] は、}元の証明の説明を行いました。それ以来、いくつかの研究で、内積などの異なるガジェットを使用して同様の定理が証明されました。^[25]扱える最小のガジェットは、 を使用したインデックス ガジェットです。^[26] Göös、Pitassi、Watson は、Raz-McKenzie 手法をランダム化プロトコルに拡張しました。^[27]${\displaystyle f\circ g}$${\displaystyle f}$${\displaystyle c=1+\epsilon }$

ラズ・マッケンジーの持ち上げ定理を単純に修正すると、を計算するためのプロトコルツリーのサイズの対数に対するの下限が得られます。ここで はの最適決定木の深さです。Garg、Göös、Kamath、Sokolov はこれをDAGのような設定に拡張し、^[28]その結果を使用して単調回路の下限を得ました。同じ手法は、証明の複雑さへの応用ももたらしました。^[29]${\displaystyle \Delta \cdot D(g)}$${\displaystyle f\circ g}$${\displaystyle \Delta }$${\displaystyle f}$

別のタイプのリフティングの例としては、シェルストフのパターン行列法^{[30]が挙げられます。この方法では、} fの近似次数に関して、g が修正されたインデックスガジェットである、の量子通信複雑性の下限が与えられます。ブール関数の近似次数とは、すべてのブール点上の関数を 1/3 の加法誤差まで近似する多項式の最小次数です。 ${\displaystyle f\circ g}$

シミュレーション法を使用する Raz-McKenzie 証明とは対照的に、Sherstov の証明はfの近似次数の二重証拠を取り、一般化ディスクレパンシー法を使用した量子クエリ複雑性の下限を与えます。fの近似次数の二重証拠は、LP 双対性を介して取得された近似次数の下限証拠です。この二重証拠は、一般化ディスクレパンシー法のデータを構成する他のオブジェクトに組み込まれます。 ${\displaystyle f\circ g}$

このアプローチの別の例としては、ピタッシとロベールの研究^[31]があり、代数的ギャップがラズボロフのランク測度の下限まで引き上げられています。その結果、通信の複雑さの観点から単調な回路サイズのカルチマー-ウィグダーソンの特徴付け^[32]によって得られた、明示的な関数の単調な回路複雑さの強い指数的下限が得られます。

0 または 1 の入力行列 を考えると、最悪の場合 を決定論的に計算するために交換される最小ビット数は、行列 のランクの対数によって下から制限されることが知られています。対数ランク予想は、通信の複雑さ が、のランクの対数の定数乗によって上から制限されることを提唱しています。D(f) は、対数ランク の多項式によって上下に制限されるため、D(f) は対数ランク と多項式的に関連していると言えます。行列のランクは行列のサイズで多項式時間で計算可能なので、このような上限により、行列の通信の複雑さを多項式時間で近似することができます。ただし、行列自体のサイズは入力のサイズに対して指数関数的であることに注意してください。 ${\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}$${\displaystyle f}$${\displaystyle D(f)}$${\displaystyle M_{f}}$${\displaystyle D(f)}$${\displaystyle M_{f}}$${\displaystyle (M_{f})}$${\displaystyle (M_{f})}$

ランダム化プロトコルの場合、最悪の場合に交換されるビット数 R(f) は、次の式と多項式的に関係していると推測されます。

${\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}$

このようなログランク予想は、行列の通信複雑さの問題を、行列の線形独立行（列）の問題にまで縮小するため、価値があります。この特定のバージョンは、ログ近似ランク予想と呼ばれ、最近、Chattopadhyay、Mande、Sherif（2019）^[33]によって、驚くほど単純な反例を使用して反証されました。これにより、たとえば上記のEQの場合、通信複雑さの問題の本質は、入力が行列のどこにあるかを把握して、それらが同等であるかどうかを確認することであることが明らかになりました。

通信複雑度の下限値は、決定木の複雑度、VLSI回路、データ構造、ストリーミングアルゴリズム、チューリングマシンの空間と時間のトレードオフなどの下限値を証明するために使用できます。^[2]

コニツァーとサンドホルム^[34]は、政治組織や非政治組織に不可欠ないくつかの一般的な投票ルールの通信複雑性を研究した。コンパイル複雑性はこれに密接に関連した概念であり、単一ラウンドの通信複雑性と見なすことができる。

• ギャップハミング問題