<p>First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman <a href="http://www.research.rutgers.edu/%7Etroyjlee/survey_plain.pdf" rel="noreferrer">Lower Bounds on Communication Complexity</a>.</p>
<blockquote>
<p><strong>Definition:</strong> Let <span class="math-container">$A$</span> be a sign matrix. The approximate rank of <span class="math-container">$A$</span> with approximation factor <span class="math-container">$\alpha$</span>, denoted <span class="math-container">$rank^\alpha(A)$</span>, is</p>
<p><span class="math-container">$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$</span>.</p>
<p>When <span class="math-container">$\alpha\to \infty$</span>, define</p>
<p><span class="math-container">$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$</span>.</p>
</blockquote>
<p>A result by <a href="http://www.sciencedirect.com/science/article/pii/0304397595000054" rel="noreferrer">Krause</a> says that <span class="math-container">$R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$</span> where <span class="math-container">$\alpha=1/(1-2\epsilon)$</span> and <span class="math-container">$R_\epsilon^{pri}$</span> is the bounded-error private-coin communication complexity of <span class="math-container">$A$</span> with error upper-bounded by <span class="math-container">$\epsilon$</span>.</p>
<p>The above was for background. Now to answer the question, <a href="http://dl.acm.org/citation.cfm?id=9117" rel="noreferrer">Paturi and Simon</a> showed that <span class="math-container">$rank^\infty(A)$</span> completely characterizes the unbounded-error communication complexity of <span class="math-container">$A$</span>. They also showed that this agrees with the minimum dimension of an arrangement realizing the boolean function whose communication matrix is <span class="math-container">$A$</span>. The unbounded-error communication complexity of the equality function is <span class="math-container">$O(1)$</span>. Keep that in mind.</p>
<p>The communication matrix for equality is just the identity, i.e., a boolean matrix with <span class="math-container">$2^n$</span> rows and <span class="math-container">$2^n$</span> columns with all ones in the diagonal. Let's denote this by <span class="math-container">$I_{2^n}$</span>. <a href="http://kam.mff.cuni.cz/%7Ematousek/cla/alon-identity.pdf" rel="noreferrer">Alon</a> showed that <span class="math-container">$rank^2(I_{2^n})=\Omega(n)$</span> which is tight up to a logarithmic factor (with the theorem by Krause we obtain <span class="math-container">$R_\epsilon^{pri}(EQ)=\Omega(\log n)$</span>).</p>
<p>The identity matrix has full rank, i.e., <span class="math-container">$2^n$</span>. Thus, we have exponentially large separations for <span class="math-container">$\alpha=2$</span> and <span class="math-container">$\alpha\to\infty$</span>.</p>

CC BY-SA 3.0
2011-11-28T03:40:59.440Z
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$.
pyao
CC BY-SA 3.0
2011-11-28T03:54:20.867Z
aah I see, but that is not written in the question. To my knowledge the largest gap is exponential.
Marcos Villagra
CC BY-SA 3.0
2011-11-28T04:04:30.130Z
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$?
Sasho Nikolov
CC BY-SA 3.0
2011-11-28T04:09:12.977Z
do you mean a gap of $\Omega(2^n)$ rather than $2^{\Omega(n)}$?
Sasho Nikolov
CC BY-SA 3.0
2011-11-28T04:24:36.213Z
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$.
Marcos Villagra
CC BY-SA 3.0
2011-11-28T02:05:41.683Z
2011-11-28T03:27:36.353Z
2020-06-17T09:38:08.363Z
Marcos Villagra
<p>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?</p>

CC BY-SA 3.0
2011-04-13T15:55:22.587Z
what is the "approximate rank" of a matrix ?
Suresh Venkat
CC BY-SA 3.0
2011-04-13T18:22:48.787Z
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$).
mjqxxxx
<co.combinatorics><linear-algebra><matrices><communication-complexity><boolean-matrix>
What is the largest gap between rank and approximate rank?
pyao
# What is the largest gap between rank and approximate rank?

(Asked by: username_0 on 2011-04-13)

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?

**Tags:** co.combinatorics, linear-algebra, matrices, communication-complexity, boolean-matrix

> **Comments:**
> **username_1**: what is the "approximate rank" of a matrix ?  
> **username_2**: 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$).  

---

## 1 answers

### Answer by username_3 on 2011-11-28. Score: 9

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](http://www.research.rutgers.edu/%7Etroyjlee/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 [Krause](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, [Paturi and Simon](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}$. [Alon](http://kam.mff.cuni.cz/%7Ematousek/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$.

> **Comments:**
> **username_0**: 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$.  
> **username_3**: aah I see, but that is not written in the question. To my knowledge the largest gap is exponential.  
> **username_4**: 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$?  
> **username_4**: do you mean a gap of $\Omega(2^n)$ rather than $2^{\Omega(n)}$?  
> **username_3**: 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$.  

---

