Quel est l'écart le plus important entre le rang et le rang approximatif?

Nous savons que le logarithme du rang d'une matrice 0-1 est la borne inférieure de la complexité de communication déterministe, et le logarithme du rang approximatif est la borne inférieure de la complexité de communication aléatoire. Le plus grand écart entre la complexité de la communication déterministe et la complexité de la communication aléatoire est exponentiel. Alors qu'en est-il de l'écart entre le rang et le rang approximatif d'une matrice booléenne?

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

quel est le "rang approximatif" d'une matrice?

Suresh Venkat

Le rang -approximate d'une matrice booléenne est le rang minimum d'une matrice réelle qui diffère de par au plus dans n'importe quelle entrée (cf. Buhrman et Wolf 2001, "La complexité de la communication limite inférieure par les polynômes"). Il serait utile de modifier la question pour expliquer cela (si c'est la définition souhaitée) et décrire le rôle de (car la différence de rangs dépend clairement de ).

ϵ

$\epsilon$

M

$M$

A

$A$

M

$M$

ϵ

$\epsilon$

ϵ

$\epsilon$

ϵ

$\epsilon$

mjqxxxx

Je vais d'abord donner quelques informations et définir le rang approximatif. Une bonne référence est la récente enquête de Lee et Schraibman Lower Bounds sur la complexité de la communication .

Définition: Soit une matrice de signes. Le rang approximatif de avec le facteur d'approximation , noté , est $A$ $A$ $\alpha$ $rank^\alpha(A)$

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

Lorsque , définissez $\alpha\to \infty$

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

Un résultat de Krause dit que où et est le complexité de la communication des pièces privées à erreur bornée de avec erreur délimitée par . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Ce qui précède était pour le fond. Maintenant , pour répondre à la question, Paturi et Simon a montré que caractérise complètement la complexité de la communication sans bornes erreur de . Ils ont également montré que cette accord avec la dimension minimum d'un dispositif réalisant la fonction booléenne dont la matrice est communication . La complexité de communication à erreur non bornée de la fonction d'égalité est . Garde cela à l'esprit. $rank^\infty(A)$ $A$ $A$ $O(1)$

La matrice de communication pour l'égalité n'est que l'identité, c'est-à-dire une matrice booléenne avec lignes et colonnes avec toutes celles dans la diagonale. Notons cela par . Alon a montré que le qui est serré jusqu'à un facteur logarithmique (avec le théorème de Krause nous obtenons ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

La matrice d'identité a un rang complet, c'est-à-dire . Ainsi, nous avons des séparations exponentiellement grandes pour et . $2^n$ $\alpha=2$ $\alpha\to\infty$

Marcos Villagra
la source

Merci. mais ma question est de savoir s'il existe un écart surexponentiel pour le et le , où mais pas .

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 je vois, mais ce n'est pas écrit dans la question. À ma connaissance, le plus grand écart est exponentiel.

Marcos Villagra

Marcos vous donne une référence qui montre un écart de entre et . comment peut-il y avoir un intervalle surexponentiel lorsque la taille de la matrice est ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

Sasho Nikolov

voulez-vous dire un écart de plutôt que ?

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

Sasho Nikolov

Sasho fait un bon point, que voulez-vous dire par "super-exponentielle? Pour tout problème de communication, la matrice est toujours sur .

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

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

Marcos Villagra

Quel est l'écart le plus important entre le rang et le rang approximatif?

Réponses: