2008/01/01 by Troy Lee, Lee, Troy, Adi Shraibman +1
Computer Science · Engineering · #Communication complexity #Complexity and Algorithms in Graphs #Quantum Computing Algorithms and Architecture #graph theory and CDMA systems #lower bounds
paper · doi:10.4230/dagsemproc.08381.3
openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ellinfty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.