An approximation algorithm for approximation rank - Computer Science > Computational ComplexityReport as inadecuate

An approximation algorithm for approximation rank - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: One of the strongest techniques available for showing lower bounds on quantumcommunication complexity is the logarithm of the approximation rank of thecommunication matrix-the minimum rank of a matrix which is entrywise close tothe communication matrix. This technique has two main drawbacks: it isdifficult to compute, and it is not known to lower bound quantum communicationcomplexity with entanglement.Linial and Shraibman recently introduced a norm, called gamma 2^{alpha}, toquantum communication complexity, showing that it can be used to lower boundcommunication with entanglement. Here the parameter alpha is a measure ofapproximation which is related to the allowable error probability of theprotocol. This bound can be written as a semidefinite program and gives boundsat least as large as many techniques in the literature, although it is smallerthan the corresponding alpha-approximation rank, rk alpha. We show that in factlog gamma 2^{alpha}A$ and log rk {alpha}A$ agree up to small factors. Ascorollaries we obtain a constant factor polynomial time approximation algorithmto the logarithm of approximate rank, and that the logarithm of approximationrank is a lower bound for quantum communication complexity with entanglement.

Author: Troy Lee, Adi Shraibman



Related documents