Composition theorems in communication complexity - Quantum PhysicsReportar como inadecuado

Composition theorems in communication complexity - Quantum Physics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: A well-studied class of functions in communication complexity are composedfunctions of the form $f \comp g^nx,y=fgx^1, y^1,

., gx^n,y^n$. Thisis a rich family of functions which encompasses many of the important examplesin the literature. It is thus of great interest to understand what propertiesof $f$ and $g$ affect the communication complexity of $f \comp g^n$, and inwhat way.Recently, Sherstov \cite{She09b} and independently Shi-Zhu \cite{SZ09b}developed conditions on the inner function $g$ which imply that the quantumcommunication complexity of $f \comp g^n$ is at least the approximatepolynomial degree of $f$. We generalize both of these frameworks. We show thatthe pattern matrix framework of Sherstov works whenever the inner function $g$is {\em strongly balanced}-we say that $g: X \times Y \to \{-1,+1\}$ isstrongly balanced if all rows and columns in the matrix $M g=gx,y {x,y}$sum to zero. This result strictly generalizes the pattern matrix framework ofSherstov \cite{She09b}, which has been a very useful idea in a variety ofsettings \cite{She08b,RS08,Cha07,LS09,CA08,BHN09}.Shi-Zhu require that the inner function $g$ has small {\em spectraldiscrepancy}, a somewhat awkward condition to verify. We relax this to theusual notion of discrepancy. We also enhance the framework of composedfunctions studied so far by considering functions $Fx,y = fgx,y$, wherethe range of $g$ is a group $G$. When $G$ is Abelian, the analogue of thestrongly balanced condition becomes a simple group invariance property of $g$.We are able to formulate a general lower bound on $F$ whenever $g$ satisfiesthis property.

Autor: Troy Lee, Shengyu Zhang


Documentos relacionados