10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ what is the "approximate rank" of a matrix ? $\endgroup$ – Suresh Venkat Apr 13 '11 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$ – mjqxxxx Apr 13 '11 at 18:22
9
$\begingroup$

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$.

$\endgroup$
  • $\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$ – pyao Nov 28 '11 at 3:40
  • $\begingroup$ aah I see, but that is not written in the question. To my knowledge the largest gap is exponential. $\endgroup$ – Marcos Villagra Nov 28 '11 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$ – Sasho Nikolov Nov 28 '11 at 4:04
  • $\begingroup$ do you mean a gap of $\Omega(2^n)$ rather than $2^{\Omega(n)}$? $\endgroup$ – Sasho Nikolov Nov 28 '11 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$ – Marcos Villagra Nov 28 '11 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.