Was ist die größte Lücke zwischen Rang und ungefährem Rang?

Wir wissen, dass das Protokoll des Ranges einer 0-1-Matrix die Untergrenze der deterministischen Kommunikationskomplexität ist, und das Protokoll des ungefähren Ranges die Untergrenze der randomisierten Kommunikationskomplexität ist. Die größte Lücke zwischen deterministischer Kommunikationskomplexität und randomisierter Kommunikationskomplexität ist exponentiell. Was ist also mit der Lücke zwischen Rang und ungefährem Rang einer booleschen Matrix?

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

Was ist der "ungefähre Rang" einer Matrix?

Suresh Venkat

Der ungefähre Rang einer booleschen Matrix ist der minimale Rang einer reellen Matrix , der sich in jedem Eintrag um höchstens von unterscheidet (vgl. Buhrman und Wolf 2001, "Kommunikationskomplexitätsuntergrenzen durch Polynome"). Es wäre hilfreich, die Frage zu bearbeiten, um dies zu erklären (wenn es die gewünschte Definition ist) und die Rolle von (da der Unterschied in den Rängen eindeutig von abhängt ).

ϵ

$\epsilon$

M

$M$

A

$A$

M

$M$

ϵ

$\epsilon$

ϵ

$\epsilon$

ϵ

$\epsilon$

mjqxxxx

Zuerst werde ich einige Hintergrundinformationen geben und den ungefähren Rang definieren. Eine gute Referenz ist die jüngste Umfrage von Lee und Schraibman Lower Bounds zur Kommunikationskomplexität .

Definition: Sei eine Vorzeichenmatrix. Der ungefähre Rang von mit dem Approximationsfaktor , bezeichnet als , ist $A$ $A$ $\alpha$ $rank^\alpha(A)$

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

Wenn , definieren Sie $\alpha\to \infty$

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

Ein Ergebnis von Krause besagt, dass wobei und ist Komplexität der privaten Münzkommunikation mit begrenztem Fehler von mit einem durch begrenzten Fehler . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Das obige war für den Hintergrund. Um die Frage zu beantworten, zeigten Paturi und Simon , dass die Kommunikationskomplexität von unbegrenzten Fehlern vollständig charakterisiert . Sie zeigten auch, dass dies mit der minimalen Dimension einer Anordnung übereinstimmt, die die Boolesche Funktion realisiert, deren Kommunikationsmatrix . Die Kommunikationskomplexität der Gleichheitsfunktion mit unbegrenzten Fehlern ist . Behalt das im Kopf. $rank^\infty(A)$ $A$ $A$ $O(1)$

Die Kommunikationsmatrix für Gleichheit ist nur die Identität, dh eine boolesche Matrix mit Zeilen und Spalten mit allen in der Diagonale. Bezeichnen wir dies mit . Alon zeigte, dass was bis zu einem logarithmischen Faktor eng ist (mit dem Satz von Krause erhalten wir ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

Die Identitätsmatrix hat den vollen Rang, dh . Wir haben also exponentiell große Abstände für und . $2^n$ $\alpha=2$ $\alpha\to\infty$

Marcos Villagra
quelle

Vielen Dank. aber meine Frage ist, ob es eine überexponentielle Lücke für und , wobei aber nicht .

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 ich verstehe, aber das steht nicht in der frage. Meines Wissens ist die größte Lücke exponentiell.

Marcos Villagra

Marcos gibt Ihnen eine Referenz, die eine Lücke von zwischen und . Wie kann es eine überexponentielle Lücke geben, wenn die Größe der Matrix beträgt ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

Sasho Nikolov

Meinst du eine Lücke von statt ?

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

Sasho Nikolov

Sasho macht einen guten Punkt, was meinst du mit "super-exponentiell? Für jedes Kommunikationsproblem ist die Matrix immer über .

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

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

Marcos Villagra

Was ist die größte Lücke zwischen Rang und ungefährem Rang?

Antworten: