An Approximation Algorithm for Approximation Rank
Troy Lee, Adi Shraibman · 2009
One of the strongest techniques available for showing lower bounds on bounded-error communication complexity is the logarithm of the approximation rank of the communication matrix-the minimum rank of a matrix which is close to the communication matrix in lscrinfinnorm. Krause showed that the logarithm of approximation rank is a lower bound in the randomized case, and later Buhrman and de Wolf showed it could also be used for quantum communication complexity. As a lower bound technique, approximation rank has two main drawbacks: it is difficult to compute, and it is not known to lower bound the model of quantum communication complexity with entanglement. Linial and Shraibman recently introduced a quantity, called gamma2alpha, to quantum communication complexity, showing that it can be used to lower bound communication in the model with shared entanglement. Here alpha is a measure of approximation which is related to the allowable error probability of the protocol. This quantity can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rkalpha. We show that in fact log gamma2alpha(A) and log rkalpha(A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximation rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.