Composition theorems in communication complexity

DOI10.1007/978-3-642-14165-2_41MaRDI QIDQ3587401zbMATH OpenOpenAlexFDO

Authors Troy Lee, Shengyu Zhang

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1443

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A well-studied class of functions in communication complexity are composed functions of the form $(fcomp{g}^n)(x,y)=f(g(x^1,y^1),\mathrm{...},g(x^n,y^n))$. This is a rich family of functions which encompasses many of the important examples in the literature. It is thus of great interest to understand what properties of $f$ and $g$ affect the communication complexity of $(fcomp{g}^n)$, and in what way. Recently, Sherstov cite{She09b} and independently Shi-Zhu cite{SZ09b} developed conditions on the inner function $g$ which imply that the quantum communication complexity of $fcomp{g}^n$ is at least the approximate polynomial degree of $f$. We generalize both of these frameworks. We show that the pattern matrix framework of Sherstov works whenever the inner function $g$ is {em strongly balanced}---we say that $g:XimesYo-1,+1$ is strongly balanced if all rows and columns in the matrix $M_g=[g(x,y){]}_{x,y}$ sum to zero. This result strictly generalizes the pattern matrix framework of Sherstov cite{She09b}, which has been a very useful idea in a variety of settings cite{She08b,RS08,Cha07,LS09,CA08,BHN09}. Shi-Zhu require that the inner function $g$ has small {em spectral discrepancy}, a somewhat awkward condition to verify. We relax this to the usual notion of discrepancy. We also enhance the framework of composed functions studied so far by considering functions $F(x,y)=f(g(x,y))$, where the range of $g$ is a group $G$. When $G$ is Abelian, the analogue of the strongly balanced condition becomes a simple group invariance property of $g$. We are able to formulate a general lower bound on $F$ whenever $g$ satisfies this property.

Recommendations

• scientific article; zbMATH DE number 5568623
• The pattern matrix method
• The NOF multiparty communication complexity of composed functions
• Lower Bounds for Quantum Communication Complexity
• scientific article; zbMATH DE number 5953454

Cited in

(18)

• Communication complexity and combinatorial lattice theory
• Counting the number of perfect matchings, and generalized decision trees
• Simulation theorems via pseudo-random properties
• The relationship between inner product and counting cycles
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
• The pattern matrix method
• Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
• On Toda’s Theorem in Structural Communication Complexity
• On the tightness of the Buhrman-Cleve-Wigderson simulation
• scientific article; zbMATH DE number 2038719 (Why is no real title available?)
• Communication complexity of permutation-invariant functions
• Approximate Degree in Classical and Quantum Computing
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• Approximate F₂-Sketching of Valuation Functions
• Rectangles are nonnegative juntas
• Around the log-rank conjecture
• Compressed communication complexity of longest common prefixes

This page was built for publication: Composition theorems in communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587401)