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

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

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
• 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)

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

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)