what is the largest gap between rank and approximate rank?

What is the largest gap between rank and approximate rank?

• 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?

• Answer:

  First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman http://www.research.rutgers.edu/~troyjlee/survey_plain.pdf. 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 http://www.sciencedirect.com/science/article/pii/0304397595000054 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, http://dl.acm.org/citation.cfm?id=9117 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}$. http://kam.mff.cuni.cz/~matousek/cla/alon-identity.pdf 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$.