Conjetura de rango logarítmico

En informática teórica , la conjetura del rango logarítmico establece que la complejidad de comunicación determinista de una función booleana de dos partes está relacionada polinómicamente con el logaritmo del rango de su matriz de entrada. ^{[ 1 ] [ 2 ]}

Dejar${\displaystyle D(f)}$denotemos la complejidad de comunicación determinista de una función, y sea${\displaystyle \operatorname {rank} (f)}$denota el rango de su matriz de entrada${\displaystyle M_{f}}$(sobre los reales). Dado que cada protocolo utiliza hasta${\displaystyle c}$particiones de bits${\displaystyle M_{f}}$en como máximo${\displaystyle 2^{c}}$rectángulos monocromáticos, y cada uno de ellos tiene un rango como máximo de 1,

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

La conjetura del rango logarítmico afirma que${\displaystyle D(f)}$También está acotada superiormente por un polinomio en el rango logarítmico: para alguna constante${\displaystyle C}$,

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

Lovett ^{[ 3 ]} demostró el límite superior

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

Esto fue mejorado por Sudakov y Tomon, ^{[ 4 ]} quienes eliminaron el factor logarítmico, demostrando que

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

Este es el mejor límite superior conocido hasta el momento.

El límite inferior más conocido, debido a Göös, Pitassi y Watson, ^{[ 5 ]} establece que${\displaystyle C\geq 2}$En otras palabras, existe una secuencia de funciones.${\displaystyle f_{n}}$, cuyo rango logarítmico tiende a infinito, de tal manera que

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

En 2019, se desmintió una versión aproximada de la conjetura sobre la comunicación aleatoria. ^{[ 6 ]}

• Lista de problemas sin resolver en informática