We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So what about the gap between rank and approximate rank of a boolean matrix?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ what is the "approximate rank" of a matrix ? $\endgroup$– Suresh VenkatApr 13, 2011 at 15:55
-
7$\begingroup$ The $\epsilon$-approximate rank of a boolean matrix $M$ is the minimum rank of a real matrix $A$ that differs from $M$ by at most $\epsilon$ in any entry (cf. Buhrman and Wolf 2001, "Communication complexity lower bounds by polynomials"). It would be helpful to edit the question to explain this (if it's the desired definition) and describe the role of $\epsilon$ (since the difference in ranks clearly depends on $\epsilon$). $\endgroup$– mjqxxxxApr 13, 2011 at 18:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman Lower Bounds on Communication Complexity.
Definition: Let $A$ be a sign matrix. The approximate rank of $A$ with approximation factor $\alpha$, denoted $rank^\alpha(A)$, is
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$.
When $\alpha\to \infty$, define
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$.
A result by Krause says that $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ where $\alpha=1/(1-2\epsilon)$ and $R_\epsilon^{pri}$ is the bounded-error private-coin communication complexity of $A$ with error upper-bounded by $\epsilon$.
The above was for background. Now to answer the question, Paturi and Simon showed that $rank^\infty(A)$ completely characterizes the unbounded-error communication complexity of $A$. They also showed that this agrees with the minimum dimension of an arrangement realizing the boolean function whose communication matrix is $A$. The unbounded-error communication complexity of the equality function is $O(1)$. Keep that in mind.
The communication matrix for equality is just the identity, i.e., a boolean matrix with $2^n$ rows and $2^n$ columns with all ones in the diagonal. Let's denote this by $I_{2^n}$. Alon showed that $rank^2(I_{2^n})=\Omega(n)$ which is tight up to a logarithmic factor (with the theorem by Krause we obtain $R_\epsilon^{pri}(EQ)=\Omega(\log n)$).
The identity matrix has full rank, i.e., $2^n$. Thus, we have exponentially large separations for $\alpha=2$ and $\alpha\to\infty$.
-
$\begingroup$ Thanks. but my question is if there is superexponential gap for $rank(A)$ and $rank^{\alpha}(A)$, where $\alpha>1$ but not $\alpha\neq\infty$. $\endgroup$– pyaoNov 28, 2011 at 3:40
-
$\begingroup$ aah I see, but that is not written in the question. To my knowledge the largest gap is exponential. $\endgroup$ Nov 28, 2011 at 3:54
-
1$\begingroup$ Marcos gives you a reference that shows a gap of $2^n/n$ between ${rank}$ and ${rank}^2$. how can there be a superexponential gap when the size of the matrix is $2^n$? $\endgroup$ Nov 28, 2011 at 4:04
-
$\begingroup$ do you mean a gap of $\Omega(2^n)$ rather than $2^{\Omega(n)}$? $\endgroup$ Nov 28, 2011 at 4:09
-
$\begingroup$ Sasho makes a good point, what do you mean with "super-exponential? For any communication problem, the matrix is always over $\{0,1\}^n \times \{0,1\}^n$. $\endgroup$ Nov 28, 2011 at 4:24