ログランク予想

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

させて${\displaystyle D(f)}$関数の決定論的通信複雑度を表し、${\displaystyle \operatorname {rank} (f)}$入力行列のランクを表す${\displaystyle M_{f}}$（実数上）。最大で${\displaystyle c}$ビットパーティション${\displaystyle M_{f}}$最大で$2c$単色の長方形であり、それぞれのランクは最大で 1 である。

${\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 ]}

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