most recent 30 from http://mathoverflow.net 2013-05-26T07:04:35Z http://mathoverflow.net/feeds/question/61782 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61782/what-is-the-largest-gap-between-rank-and-approximate-rank Penghui Yao 2011-04-15T04:58:11Z 2011-04-15T04:58:11Z

<p>$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} with a $(1,-1)$ matrix $M_f$ of size $|X|\times |Y|$. We know the log of rank of $M_f$ is lower bound of deterministic communication complexity of $f$ and the log of approximation rank of $M_f$ is lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So how about the largest gap between rank and approximation rank?</p>