Conjetura del 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 polinomialmente con el logaritmo del rango de su matriz de entrada. ^{[1] [2]}

Denotemos la complejidad de comunicación determinista de una función, y denotemos el rango de su matriz de entrada (sobre los reales). Dado que cada protocolo que usa hasta bits se divide en como máximo rectángulos monocromáticos, y cada uno de estos tiene rango como máximo 1,${\ Displaystyle D (f)}$${\ Displaystyle \ operatorname {rango} (f)}$${\ Displaystyle M_ {f}}$${\ Displaystyle c}$${\ Displaystyle M_ {f}}$${\ Displaystyle 2 ^ {c}}$

La conjetura del rango logarítmico establece que también está limitada por un polinomio en el rango logarítmico: para alguna constante ,${\ Displaystyle D (f)}$${\ Displaystyle C}$

El límite inferior más conocido, debido a Göös, Pitassi y Watson, ^[4] establece que . En otras palabras, existe una secuencia de funciones , cuyo log-rank llega al infinito, de modo que${\ Displaystyle C \ geq 2}$${\ Displaystyle f_ {n}}$

---