Composition theorems in communication complexity

DOI10.1007/978-3-642-14165-2_41zbMATH Open1288.68065arXiv1003.1443OpenAlexW2114806597MaRDI QIDQ3587401FDOQ3587401

Authors: Troy Lee, Shengyu Zhang 

Publication date: 7 September 2010

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

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.

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

Recommendations

• scientific article
• The pattern matrix method
• The NOF multiparty communication complexity of composed functions
• Lower Bounds for Quantum Communication Complexity
• scientific article

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)

Cited In (18)

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

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)