¿Cuál es la brecha más grande entre el rango y el rango aproximado?

Sabemos que el registro del rango de una matriz 0-1 es el límite inferior de la complejidad de comunicación determinista, y el registro del rango aproximado es el límite inferior de la complejidad de la comunicación aleatoria. La brecha más grande entre la complejidad de comunicación determinista y la complejidad de comunicación aleatoria es exponencial. Entonces, ¿qué pasa con la brecha entre el rango y el rango aproximado de una matriz booleana?

co.combinatorics linear-algebra matrices communication-complexity boolean-matrix pyao
fuente

¿Cuál es el "rango aproximado" de una matriz?

Suresh Venkat

El rango aproximado

ϵ

$\epsilon$ de una matriz booleana

M

$M$ es el rango mínimo de una matriz real

A

$A$ que difiere de

M

$M$ como máximo en

ϵ

$\epsilon$ en cualquier entrada (cf. Buhrman y Wolf 2001, "Límites inferiores de complejidad de comunicación por polinomios"). Sería útil editar la pregunta para explicar esto (si es la definición deseada) y describir el papel de

ϵ

$\epsilon$ (ya que la diferencia en los rangos depende claramente de

ϵ

$\epsilon$ ).

mjqxxxx

Primero daré algunos antecedentes y definiré el rango aproximado. Una buena referencia es la encuesta reciente de Lee y Schraibman Lower Bounds sobre la complejidad de la comunicación .

$A$ $A$ $\alpha$ $rank^\alpha(A)$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$

Cuando , defina $\alpha\to \infty$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$ .

Un resultado de Krause dice que donde y es el complejidad de comunicación de moneda privada de error acotado de con error acotado superiormente por . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Lo anterior fue para el fondo. Ahora, para responder a la pregunta, Camas y Simon demostraron que caracteriza por completo la complejidad comunicación sin límites de errores de . También demostraron que este está de acuerdo con la dimensión mínima de una disposición de la realización de la función booleana cuya matriz es la comunicación . La complejidad de comunicación de error ilimitado de la función de igualdad es . Mantenlo en mente. $rank^\infty(A)$ $A$ $A$ $O(1)$

La matriz de comunicación para la igualdad es solo la identidad, es decir, una matriz booleana con filas y columnas con todas en diagonal. Denotemos esto por . Alon mostró que el que está estrechamente relacionado con un factor logarítmico (con el teorema de Krause obtenemos ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

La matriz de identidad tiene rango completo, es decir, . Por lo tanto, tenemos separaciones exponencialmente grandes para y . $2^n$ $\alpha=2$ $\alpha\to\infty$

Marcos Villagra
fuente

Gracias. pero mi pregunta es si hay una brecha superexponencial para el y el , donde pero no .

r a n k (A)

$rank(A)$

r a n k^{α} (A)

$rank^{\alpha}(A)$

α > 1

$\alpha>1$

α \neq \infty

$\alpha\neq\infty$

pyao

aah ya veo, pero eso no está escrito en la pregunta. Que yo sepa, la brecha más grande es exponencial.

Marcos Villagra

Marcos le da una referencia que muestra una brecha de entre y . ¿Cómo puede haber una brecha superexponencial cuando el tamaño de la matriz es ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

Sasho Nikolov

¿te refieres a una brecha de lugar de ?

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

Sasho Nikolov

Sasho hace un buen punto, ¿qué quieres decir con "super-exponencial? Para cualquier problema de comunicación, la matriz siempre está sobre .

{0, 1}^{n} \times {0, 1}^{n}

$\{0,1\}^n \times \{0,1\}^n$

Marcos Villagra

¿Cuál es la brecha más grande entre el rango y el rango aproximado?

Respuestas: