Editing Communication complexity (section)

== Open problems ==

Considering a 0 or 1 input matrix <math>M_f=[f(x,y)]_{x,y\in \{0,1\}^n}</math>, the minimum number of bits exchanged to compute <math>f</math> deterministically in the worst case, <math>D(f)</math>, is known to be bounded from below by the logarithm of the [[Rank (linear algebra)|rank]] of the matrix <math>M_f</math>. 
The [[Log-rank conjecture|log rank conjecture]] proposes that the communication complexity, <math>D(f)</math>, is bounded from above by a constant power of the logarithm of the rank of <math>M_f</math>. Since D(f) is bounded from above and below by polynomials of log rank<math>(M_f)</math>, we can say D(f) is polynomially related to log rank<math>(M_f)</math>. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.

For a randomized protocol, the number of bits exchanged in the worst case, R(f), was conjectured to be polynomially related to the following formula:

: <math>\log \min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3).</math>

Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This particular version, called the Log-Approximate-Rank Conjecture, was recently refuted by Chattopadhyay, Mande and Sherif (2019)<ref>Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.https://doi.org/10.1145/3313276.3316353</ref> using a surprisingly simple counter-example. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.