$\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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
