ログランク予想

理論計算機科学において、ログランク予想は、 2者間ブール関数の決定論的通信複雑さは、その入力行列のランクの対数と多項式的に関係しているというものである。^{[1] [2]}

関数の決定論的通信複雑度をとし、入力行列の階数（実数上）を とする。最大ビットを使用するすべてのプロトコルは最大で単色の長方形に分割され、これらの長方形の階数は最大で1であるため、 ${\displaystyle D(f)}$ ${\displaystyle \operatorname {rank} (f)}$ ${\displaystyle M_{f}}$ ${\displaystyle c}$ ${\displaystyle M_{f}}$ ${\displaystyle 2^{c}}$

${\displaystyle D(f)\geq \log _{2}\operatorname {rank} (f).}$

対数ランク予想は、対数ランクの多項式によっても上限が定められることを述べている。つまり、ある定数に対して、 ${\displaystyle D(f)}$ ${\displaystyle C}$

${\displaystyle D(f)=O((\log \operatorname {rank} (f))^{C}).}$

ラヴェット ^[3] は上限を証明した

${\displaystyle D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\log \operatorname {rank} (f)\right).}$

これはスダコフとトモン^[4]によって改良され、対数係数を除去して、

${\displaystyle D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\right).}$

これは現在知られている最良の上限です。

最もよく知られている下限は、Göös、Pitassi、Watson ^[5]によるもので、 と述べている。言い換えれば、対数階数が無限大になる関数の列が存在し、 ${\displaystyle C\geq 2}$ ${\displaystyle f_{n}}$

${\displaystyle D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).}$

2019年には、ランダム通信に関する予想の近似バージョンが反証されました。^[6]

参照

• コンピュータサイエンスにおける未解決問題の一覧

参考文献

1. Lovász, László ; Saks, Michael (1988), Möbius Functions and Communication Complexity , Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, pp.  81– 90
2. Lovett, Shachar (2014年2月)、「通信複雑性におけるログランク予想の最近の進歩」、Bulletin of the EATCS、112、arXiv : 1403.8106
3. Lovett, Shachar (2016年3月)、「コミュニケーションはランクのルートによって制限される」、Journal of the ACM、63 (1): 1:1–1:9、arXiv : 1306.1877、doi :10.1145/2724704、S2CID  47394799
4. Sudakov, Benny ; Tomon, Istvan (2023年11月30日). 「行列の不一致とログランク予想」. arXiv : 2311.18524 [数学].
5. Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2018)、「決定論的通信とパーティション番号」、SIAM Journal on Computing、47 (6): 2435– 2450、doi :10.1137/16M1059369
6. Chattopadhyay, Arkadev; Mande, Nikhil; Sherif, Suhail (2019), The Log-approximate-Rank Conjecture is False、Annual ACM Symposium on the Theory of Computing、アリゾナ州フェニックス、米国