An approximation algorithm for approximation rank - Computer Science > Computational ComplexityReportar como inadecuado

An approximation algorithm for approximation rank - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Troy Lee, Adi Shraibman


Documentos relacionados