11institutetext: Rutgers University, 11email<EMAIL_ADDRESS>22institutetext: The Chinese University of Hong Kong, 22email:
<EMAIL_ADDRESS>
# Composition theorems in communication complexity

Troy Lee 11 Shengyu Zhang 22

###### Abstract

A well-studied class of functions in communication complexity are composed
functions of the form $(f\circ
g^{n})(x,y)=f(g(x^{1},y^{1}),\ldots,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 $(f\circ g^{n})$, and in what way.

Recently, Sherstov [She09] and independently Shi-Zhu [SZ09b] developed
conditions on the inner function $g$ which imply that the quantum
communication complexity of $f\circ 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 strongly balanced—we say that $g:X\times Y\rightarrow\\{-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 [She09], which has been a very useful idea in a variety of settings
[She08b, RS08, Cha07, LS09a, CA08, BHN09].

Shi-Zhu require that the inner function $g$ has small 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.

##  1 Introduction

Communication complexity studies the minimum amount of communication needed to
compute a function whose input variables are distributed between two or more
parties. Since the introduction by Yao [Yao79] of an elegant mathematical
model to study this question, communication complexity has grown into a rich
field both because of its inherent mathematical interest and also its
application to many other models of computation. See the textbook of
Kushilevitz and Nisan [KN97] for a comprehensive introduction to the field.

In analogy with traditional computational complexity classes, one can consider
different models of communication complexity based on the resources available
to the parties. Besides the standard deterministic model, of greatest interest
to us will be a randomized version of communication complexity, where the
parties have access to a source of randomness and are allowed to err with some
small constant probability, and a quantum model where the parties share a
quantum channel and the cost is measured in qubits.

Several major open questions in communication complexity ask about how
different complexity measures relate to each other. The log rank conjecture,
formulated by Lovász and Saks [LS88], asks if the deterministic communication
complexity of a Boolean function $F:X\times Y\rightarrow\\{0,1\\}$ is upper
bounded by a polynomial in the logarithm of the rank of the matrix
$[F(x,y)]_{x,y}$. Another major open question is if randomized and quantum
communication complexity are polynomially related for all total functions. We
should mention here that the assumption of the function being total is crucial
as an exponential separation is known for a partial function [Raz99].

One approach to these questions has been to study them for restricted classes
of functions. Many functions of interest are block composed functions. For
finite sets $X,Y$, and $E$, a function $f:E^{n}\rightarrow\\{-1,+1\\}$, and a
function $g:X\times Y\rightarrow E$, the block composition of $f$ and $g$ is
the function $f\circ g^{n}:X^{n}\times Y^{n}\to\\{-1,+1\\}$ defined by
$(f\circ g^{n})(x,y)=f(g(x^{1},y^{1}),\ldots,g(x^{n},y^{n}))$ where
$(x^{i},y^{i})\in X\times Y$ for all $i=1,\ldots,n$. For example, if
$E=\\{-1,+1\\}$, the inner product function results when $f$ is PARITY and $g$
is AND, set-intersection when $f$ is OR and $g$ is AND, and the equality
function when $f$ is AND and $g$ is the function IS-EQUAL, which is one if and
only if $x=y$.

In a seminal paper, Razborov [Raz03] gave tight bounds for the bounded-error
quantum communication complexity of block composed functions where the outer
function $f$ is symmetric and the inner function $g$ is bitwise AND. In
particular, this result showed that randomized and quantum communication
complexity are polynomially related for such functions.

More recently, very nice frameworks have been developed by Sherstov [She07,
She09] and independently by Shi and Zhu [SZ09b] to bound the quantum
complexity of block composed functions that goes beyond the case of symmetric
$f$ to work for any $f$ provided the inner function $g$ satisfies certain
technical conditions. When $g$ satisfies these conditions, this framework
allows one to lower bound the quantum communication complexity of $f\circ
g^{n}$ in terms of the approximate polynomial degree of $f$, a classically
well-studied measure. Shi and Zhu are able to get a bound on $f\circ g^{n}$ in
terms of the approximate degree of $f$ whenever $g$ is sufficiently
“hard”—unfortunately, the hardness condition they need is in terms of
“spectral discrepancy,” a quantity which is somewhat difficult to bound, and
their bound requires that $g$ is a function on at least $\Omega(\log(n/d))$
bits, where $d$ is the approximate polynomial degree of $f$. Because of this,
Shi-Zhu are only able to reproduce Razborov’s results with a polynomially
weaker bound.

Sherstov developed so-called pattern matrices which are the matrix
representation of a block composed function when $g$ is a fixed function of a
particularly nice form. Namely, in a pattern matrix the inner function
$g:\\{-1,+1\\}^{k}\times([k]\times\\{-1,+1\\})\to\\{-1,+1\\}$ is parameterized
by a positive integer $k$ and defined by $g(x,(i,b))=x_{i}\cdot b$, where
$x_{i}$ denotes the $i^{th}$ bit of $x$. In other words, the first argument of
$g$ is a $k$ bit string $x$, and the second argument selects a bit of $x$ or
its negation. So here $X=\\{-1,+1\\}^{k}$, $Y=[k]\times\\{-1,+1\\}$ and the
intermediate set $E$ is $\\{-1,+1\\}$. With this $g$, Sherstov shows that the
approximate polynomial degree of $f$ is a lower bound on the quantum
communication complexity of $f\circ g^{n}$, for any function $f$. Though
seemingly quite special, pattern matrices have proven to be an extremely
useful concept. First, they give a simple proof of Razborov’s tight lower
bounds for $f(x\wedge y)$ for symmetric $f$. Second, they have also found many
other applications in unbounded-error communication complexity [She08b, RS08]
and have been successfully extended to multiparty communication complexity
[Cha07, LS09a, CA08, BHN09].

A key step in both the works of Sherstov and Shi-Zhu is to bound the spectral
norm of a sum of matrices $\|\sum_{i}{B_{i}}\|$. This is the major step where
these works differ. Shi-Zhu apply the triangle inequality to bound this as
$\|\sum_{i}{B_{i}}\|\leq\sum_{i}\|B_{i}\|$. On the other hand, Sherstov
observes that in the case of pattern matrices the terms of this sum are
mutually orthogonal, i.e. $B_{i}^{\dagger}B_{j}=B_{i}B_{j}^{\dagger}=0$ for
all $i\neq j$. In this case, one has a stronger bound on the spectral norm
$\|\sum_{i}{B_{i}}\|=\max_{i}\|B_{i}\|$.

In this paper, we extend both of the frameworks of Sherstov and Shi-Zhu. In
the case of Shi-Zhu, we are able to reprove their theorem with the usual
notion of discrepancy instead of the somewhat awkward spectral discrepancy
they use. The main observation we make is that as all Shi-Zhu use in this step
is the triangle inequality, we can repeat the argument with any norm here,
including discrepancy itself.

In the case of pattern matrices, special properties of the spectral norm are
used, namely the fact about the spectral norm of a sum of orthogonal matrices.
We step back to see what key features of a pattern matrix lead to this
orthogonality property. We begin with the Boolean case, that is, where the
intermediate set $E$ is taken to be $\\{-1,+1\\}$. In this case, a crucial
concept is the notion of a strongly balanced function. We say that $g:X\times
Y\rightarrow\\{-1,+1\\}$ is strongly balanced if in the sign matrix
$M_{g}[x,y]=g(x,y)$ all rows and all columns sum to zero. We show that
whenever the inner function $g$ is strongly balanced, the key orthogonality
condition holds; this implies that whenever $g$ is strongly balanced and the
communication matrix of $g$ has rank larger than one, the approximate degree
of the outer function $f$ is a lower bound on the quantum communication
complexity of $f\circ g^{n}$.

The requirement that the communication matrix of $g$ has rank larger than one
is necessary for such a statement. For example, when $g(x,y)=\oplus(x,y)$ is
the XOR function on one bit, then the communication complexity of
$\mathrm{PARITY}\circ g^{n}$ is constant, while PARITY has linear approximate
polynomial degree. It turns out that when $g$ is rank-one, the appropriate
measure of the complexity of $f\circ g^{n}$ is no longer the approximate
degree of $f$, but the minimum $\ell_{1}$ norm of Fourier coefficients of a
function entrywise close to $f$; see the survey [LS09b] for a description of
this case.

We also consider the general case where the intermediate set is any group $G$.
That is, we consider functions $F(x,y)=f(g(x,y))$, where $g:X\times
Y\rightarrow G$ for a group $G$ and $f:G\rightarrow\\{-1,+1\\}$ is a class
function on $G$. The case $E=\\{-1,+1\\}$ discussed above corresponds to
taking the group $G=\mathbb{Z}_{2}^{n}$. When $G$ is a general Abelian group,
the key orthogonality condition requires more than that the matrix
$M_{g}[x,y]=g(x,y)$ is strongly balanced; still, it admits a nice
characterization in terms of group invariance. A multiset $T\in G\times G$ is
said to be $G$-invariant if $(s,s)T=T$ for all $s\in G$. The orthogonality
condition will hold if and only if all pairs of rows and all pairs of columns
of $M_{g}$ (when viewed as multisets) are $G$\- invariant. One can generalize
the results discussed above to this general setting with appropriate
modifications. In the case that $G=\mathbb{Z}_{2}^{n}$, the $G$-invariant
condition degenerates to the strongly balanced requirement of $M_{g}$.

##  2 Preliminaries

All logarithms are base two. For a complex number $z=a+ib$ we let
$\bar{z}=a-ib$ denote the complex conjugate of $z$ and
$|z|=\sqrt{a^{2}+b^{2}}$ and $\mathrm{Re}(z)=a$.

###  2.1 Complexity measures

We will make use of several complexity measures of functions and matrices. Let
$f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$ be a function. For
$T\subseteq\\{0,1\\}^{n}$, the Fourier coefficient of $f$ corresponding to the
character $\chi_{T}$ is
$\hat{f}_{T}=\frac{1}{2^{n}}\sum_{x}f(x)\chi_{T}(x)=\frac{1}{2^{n}}\sum_{x}f(x)\prod_{i\in
T}x_{i}.$ The degree of $f$ as a polynomial, denoted $\deg(f)$, is the size of
a largest set $T$ for which $\hat{f}_{T}\neq 0$.

We will need some notations for matrices. We reserve $J$ for the all ones
matrix, whose size will be determined by the context. For a matrix $A$ let
$A^{\dagger}$ denote the conjugate transpose of $A$. We use $A\bullet B$ for
the entrywise product of $A,B$, and $A\otimes B$ for the tensor product. If
$A$ is an $m$-by-$n$ matrix then we say that $\mathrm{size}(A)=mn$. We use
$\langle A,B\rangle=\mathrm{Tr}(AB^{\dagger})$ for the inner product of $A$
and $B$.

Let $\|A\|_{1}$ be the $\ell_{1}$ norm of $A$, i.e. sum of the absolute values
of entries of $A$, and $\|A\|_{\infty}$ the $\ell_{\infty}$ norm. For a
positive semidefinite matrix $M$ let
$\lambda_{1}(M)\geq\cdots\geq\lambda_{n}(M)\geq 0$ be the eigenvalues of $M$.
We define the $i^{th}$ singular value of $A$, denoted $\sigma_{i}(A)$, as
$\sigma_{i}(A)=\sqrt{\lambda_{i}(AA^{\dagger})}$. The rank of $A$, denoted
$\mathrm{rk}(A)$ is the number of nonzero singular values of $A$. We will use
several matrix norms. The spectral or operator norm is the largest singular
value $\|A\|=\sigma_{1}(A)$, the trace norm is the summation of all singular
values $\|A\|_{tr}=\sum_{i}\sigma_{i}(A)$, and the Frobenius norm is the
$\ell_{2}$ norm of the singular values
$\|A\|_{F}=\sqrt{\sum_{i}\sigma_{i}(A)^{2}}$.

When $AB^{\dagger}=A^{\dagger}B=0$ we will say that $A,B$ are orthogonal.
Please note the difference with the common use of this term, which usually
means $\langle A,B\rangle=0$. The following facts are easily seen.

###### Fact 2.1

Let $A,B$ be two matrices of the same dimensions and suppose that
$AB^{\dagger}=A^{\dagger}B=0$. Then

$\displaystyle\mathrm{rk}(A+B)=\mathrm{rk}(A)+\mathrm{rk}(B),\
\|A+B\|_{tr}=\|A\|_{tr}+\|B\|_{tr},\ \|A+B\|=\max\\{\|A\|,\|B\|\\}.$

Another norm we will use is the $\gamma_{2}$ norm, introduced to complexity
theory in [LMSS07], and familiar in matrix analysis as the Schur product
operator norm. The $\gamma_{2}$ norm can be viewed as a weighted version of
the trace norm.

###### Definition 1

$\gamma_{2}(A)=\max_{u,v:\|u\|=\|v\|=1}\|A\bullet uv^{\dagger}\|_{tr}.$

Here $A\bullet B$ denotes the entrywise product of $A$ and $B$. It is clear
from this definition that $\gamma_{2}(A)\geq\|A\|_{tr}/\sqrt{mn}$ for a
$m$-by-$n$ matrix $A$.

For a norm $\Phi$, the dual norm $\Phi^{*}$ is defined as
$\Phi^{*}(v)=\max_{u:\Phi(u)\leq 1}|\langle u,v\rangle|$. For example, the
$\ell_{\infty}$ norm is dual to the $\ell_{1}$ norm, and the spectral norm is
dual to the trace norm.

The norm $\gamma_{2}^{*}$, dual to the $\gamma_{2}$ norm, looks as follows.

###### Definition 2

$\gamma_{2}^{*}(A)=\max_{\begin{subarray}{c}u_{i},v_{j}\\\
\|u_{i}\|=\|v_{j}\|=1\end{subarray}}\sum_{i,j}A[i,j]\langle
u_{i},v_{j}\rangle.$

Another complexity measure we will make use of is discrepancy

###### Definition 3

Let $A$ be an $m$-by-$n$ sign matrix and let $P$ be a probability distribution
on the entries of $A$. The discrepancy of $A$ with respect to $P$, denoted
$\mathrm{disc}_{P}(A)$, is defined as

$\mathrm{disc}_{P}(A)=\max_{\begin{subarray}{c}x\in\\{0,1\\}^{m}\\\
y\in\\{0,1\\}^{n}\end{subarray}}|x^{\dagger}A\bullet Py|.$

We will write $\mathrm{disc}_{U}(A)$ for the special case where $P$ is the
uniform distribution. It is easy to see from this definition that
$\mathrm{disc}_{U}(A)\leq\frac{\|A\|}{\sqrt{\mathrm{size}(A)}}.$ Shaltiel
[Sha03] has shown the deeper result that this bound is in fact polynomially
tight:

######  Theorem 2.2 (Shaltiel)

Let $A$ be a sign matrix. Then

$\frac{1}{108}\left(\frac{\|A\|}{\sqrt{\mathrm{size}(A)}}\right)^{3}\leq\mathrm{disc}_{U}(A).$

Discrepancy and the $\gamma_{2}^{*}$ norm are very closely related. Linial and
Shraibman [LS09c] observed that Grothendieck’s inequality gives the following.

######  Theorem 2.3 (Linial-Shraibman)

For any sign matrix $A$ and probability distribution $P$

$\mathrm{disc}_{P}(A)\leq\gamma_{2}^{*}(A\bullet P)\leq
K_{G}\;\mathrm{disc}_{P}(A)$

where $1.67\ldots\leq K_{G}\leq 1.78\ldots$ is Grothendieck’s constant.

#### Approximate measures

We will also use approximate versions of these complexity measures which come
in handy when working with bounded-error models. Say that a function $g$ gives
an $\epsilon$-approximation to $f$ if $|f(x)-g(x)|\leq\epsilon$ for all
$x\in\\{-1,+1\\}^{n}$. The $\epsilon$-approximate polynomial degree of $f$,
denoted $\deg_{\epsilon}(f)$, is the minimum degree of a function $g$ which
gives an $\epsilon$-approximation to $f$.

We will similarly look at the $\epsilon$-approximate version of the trace and
$\gamma_{2}$ norms. We give the general definition with respect to any norm.

######  Definition 4 (approximation norm)

Let $\Phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be an arbitrary norm. Let
$v\in\mathbb{R}^{n}$ be a sign vector. For $0\leq\epsilon<1$ we define the
approximation norm $\Phi^{\epsilon}$ as

$\Phi^{\epsilon}(v)=\min_{\begin{subarray}{c}u\\\
\|v-u\|_{\infty}\leq\epsilon\end{subarray}}\Phi(u).$

Notice that an approximation norm $\Phi^{\epsilon}$ is not itself a norm— we
have only defined it for sign vectors, and it will in general not satisfy the
triangle inequality.

As a norm is a convex function, using the separating hyperplane theorem one
can quite generally give the following equivalent dual formulation of an
approximation norm.

###### Proposition 1

Let $v\in\mathbb{R}^{n}$ be a sign vector, and $0\leq\epsilon<1$

$\Phi^{\epsilon}(v)=\max_{u}\frac{|\langle
v,u\rangle|-\epsilon\|u\|_{1}}{\Phi^{*}(u)}$

A proof of this can be found in the survey [LS09b].

###  2.2 Communication complexity

Let $X,Y,S$ be finite sets and $f:X\times Y\rightarrow S$ be a function. We
will let $D(f)$ be the deterministic communication complexity of $f$, and
$R_{\epsilon}(f)$ denote the randomized public coin complexity of $f$ with
error probability at most $\epsilon$. We refer to the reader to [KN97] for a
formal definition of these models. We will also study $Q_{\epsilon}(f)$ and
$Q_{\epsilon}^{*}(f)$, the $\epsilon$-error quantum communication complexity
of $f$ without and with shared entanglement, respectively. We refer the reader
to [Raz03] for a nice description of these models.

For notational convenience, we will identify a function $f:X\times
Y\rightarrow\\{-1,+1\\}$ with its sign matrix $M_{f}=[f(x,y)]_{x,y}$. Thus,
for example, $\|f\|$ refers to the spectral norm of the sign matrix
representation of $f$.

For all of our lower bound results we will actually lower bound the
approximate trace norm or $\gamma_{2}$ norm of the function. Razborov showed
that the approximate trace norm can be used to lower bound on quantum
communication complexity, and Linial and Shraibman generalized this to the
$\gamma_{2}$ norm.

######  Theorem 2.4 (Linial-Shraibman [LS09d])

Let $A$ be a sign matrix and $0\leq\epsilon<1/2$. Then

$Q_{\epsilon}^{*}(A)\geq\log\left(\gamma_{2}^{2\epsilon}(A)\right)-2.$

#### Composed functions

Before discussing lower bounds on a block composed function $f\circ g^{n}$,
let us see what we expect the complexity of such a function to be. A
fundamental idea going back to Nisan [Nis94] and Buhrman, Cleve, and Wigderson
[BCW98], is that the complexity of $f\circ g^{n}$ can be related to the
decision tree complexity, also known as query complexity, of $f$ and the
communication complexity of $g$. Let $\mathrm{DT}(f)$ be the query complexity
of $f$, that is the number of queries of the form $x_{i}=?$ needed to evaluate
$f(x)$ in the worst case. Similarly, let
$\mathrm{RT}_{\epsilon}(f),\mathrm{QT}_{\epsilon}(f)$ denote the randomized
and quantum query complexity of $f$ respectively, with error probability at
most $\epsilon$. For formal definitions of these measures and a survey of
query complexity we recommend Buhrman and de Wolf [BW02].

######  Theorem 2.5 (Nisan [Nis94], Buhrman-Cleve-Wigderson [BCW98])

For any two Boolean functions $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$ and
$g:X\times Y\rightarrow\\{-1,+1\\}$,

$\displaystyle D(f\circ g^{n})$ $\displaystyle=O(\mathrm{DT}(f)D(g))$
$\displaystyle R_{1/4}(f\circ g^{n})$
$\displaystyle=O(\mathrm{RT}_{1/4}(f)R_{1/4}(g)\log\mathrm{RT}_{1/4}(f))$
$\displaystyle Q_{1/4}(f\circ g^{n})$
$\displaystyle=O(\mathrm{QT}_{1/4}(f)Q_{1/4}(g)\log n).$

One advantage of working with block composed functions in light of this upper
bound is that query complexity is in general better understood than
communication complexity. In particular, a polynomial relationship between
deterministic query complexity and degree, and randomized and quantum query
complexities and approximate degree is known.

######  Theorem 2.6 ([NS94, BBC+01])

Let $f:\\{0,1\\}^{n}\rightarrow\\{-1,+1\\}$. Then

$\displaystyle\mathrm{DT}(f)=O(\deg(f)^{4}),\quad\mathrm{DT}(f)=O(\deg_{1/4}(f)^{6})$

Using this result together with Theorem 2.5 gives the following corollary:

###### Corollary 1

$\displaystyle D(f\circ g^{n})$ $\displaystyle=O(\deg(f)^{4}D(g)),\quad
R_{1/4}(f\circ g^{n})=O(\deg_{1/4}(f)^{6}R_{1/4}(g)\log\deg_{1/4}(f))$

Our goal, then, in showing lower bounds on the complexity of a block composed
function $f\circ g^{n}$ is to get something at least in the ballpark of this
upper bound. Of course, this is not always possible — the protocol given by
Theorem 2.5 is not always optimal. For example, when $f$ is the PARITY
function on $n$ bits, and $g(x,y)=\oplus(x,y)$ this protocol just gives an
upper bound of $n$ bits, when the true complexity is constant. See recent
results by Zhang [Zha09] and Sherstov [She10] for discussions on the tightness
of the bounds in Theorem 2.5.

##  3 Rank of block composed functions

We begin by analyzing the rank of a block composed function $f\circ g^{n}$
when the inner function $g$ is strongly balanced. This case will illustrate
the use of the strongly balanced assumption, and is simpler to understand than
the bounded-error situation treated in the next section.

Let us first formally state the definition of strongly balanced.

######  Definition 5 (strongly balanced)

Let $A$ be a sign matrix, and $J$ be the all ones matrix of the same
dimensions as $A$. We say that $A$ is balanced if
$\mathrm{Tr}(AJ^{\dagger})=0$. We further say that $A$ is strongly balanced if
$AJ^{\dagger}=A^{\dagger}J=0$. In words, a sign matrix is strongly balanced if
the sum over each row is zero, and similarly the sum over each column is zero.
We will say that a two-variable Boolean function is balanced or strongly
balanced if its sign matrix representation is.

###### Theorem 3.1

Let $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$ be an arbitrary function, and
let $g$ be a strongly balanced function. Then

$\mathrm{rk}(M_{f\circ g^{n}})=\sum_{\begin{subarray}{c}T\subseteq[n],\
\hat{f}_{T}\neq 0\end{subarray}}\mathrm{rk}(M_{g})^{|T|}.$

###### Proof

Let us write out the sign matrix for $\chi_{T}\circ g^{n}$ explicitly. If we
let $M_{g}^{0}=J$ be the all ones matrix and $M_{g}^{1}=M_{g}$, then we can
nicely write the sign matrix representing
$\chi_{T}(g(x^{1},y^{1}),\ldots,g(x^{n},y^{n}))$ as

$M_{\chi_{T}\circ g^{n}}=\bigotimes_{i}M_{g}^{T[i]}$

where $T[i]=1$ if $i\in T$ and $0$ otherwise.

We see that the condition on $g$ implies $M_{\chi_{T}\circ
g^{n}}M_{\chi_{S}\circ g^{n}}^{\dagger}=0$ if $S\neq T$. Indeed,

$\displaystyle M_{\chi_{T}\circ g^{n}}M_{\chi_{S}\circ g^{n}}^{\dagger}$
$\displaystyle=\left(\bigotimes_{i}M_{g}^{T[i]}\right)\left(\bigotimes_{i}M_{g}^{S[i]}\right)^{\dagger}$
$\displaystyle=\bigotimes_{i}\left(M_{g}^{T[i]}(M_{g}^{S[i]})^{\dagger}\right)=0.$

This follows since, by the assumption $S\neq T$, there is some $i$ for which
$S[i]\neq T[i]$ which means that this term is either $M_{g}J^{\dagger}=0$ or
$JM_{g}^{\dagger}=0$ because $g$ is strongly balanced. The other case follows
similarly.

Now that we have established this property, we can use Fact 2.1 to obtain

$\displaystyle\mathrm{rk}(M_{f\circ g^{n}})$
$\displaystyle=\mathrm{rk}\Big{(}\sum_{T\subseteq[n]}\hat{f}_{T}\chi_{T}(g(x^{1},y^{1}),\ldots,g(x^{n},y^{n}))\Big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}T\subseteq[n]\\\ \hat{f}_{T}\neq
0\end{subarray}}\mathrm{rk}(M_{\chi_{T}\circ g^{n}})$
$\displaystyle=\sum_{\begin{subarray}{c}T\subseteq[n]\\\ \hat{f}_{T}\neq
0\end{subarray}}\mathrm{rk}(M_{g})^{|T|}$

In the last step we used the fact that rank is multiplicative under tensor
product.

Theorem 3.1 has the following implication for the log rank conjecture of the
composed function with the assumption of the same conjecture for the inner
function.

###### Corollary 2

Let $X,Y$ be finite sets, $g:X\times Y\rightarrow\\{-1,+1\\}$ be a strongly
balanced function, and $M_{g}[x,y]=g(x,y)$ be the corresponding sign matrix.
Let $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$ be an arbitrary function. Assume
that $\mathrm{rk}(M_{g})\geq 2$ and further suppose that there is a constant
$c$ such that $D(g)\leq(\log\mathrm{rk}(M_{g}))^{c}$. Then

$D(f\circ g^{n})=O(\log\mathrm{rk}(f\circ g)^{4+c}).$

###### Proof

By Corollary 1, $D(f\circ
g^{n})=O(\deg(f)^{4}D(g))=O(\deg(f)^{4}(\log\mathrm{rk}(M_{g}))^{c})$. Now, it
follows from Theorem 3.1 that $\log\mathrm{rk}(f\circ
g)\geq\deg(f)\log\mathrm{rk}(M_{g})$ as by definition of degree there is some
$T\subseteq\\{0,1\\}^{n}$ with $|T|=\deg(f)$ and $\hat{f}_{T}\neq 0$.

In particular, this Corollary means that whenever $g$ is a strongly balanced
function on a constant number of bits and $\mathrm{rk}(M_{g})>1$, then the log
rank conjecture holds for $f\circ g^{n}$. If $g$ is strongly balanced and
$\mathrm{rk}(M_{g})=1$ then, up to permutation of rows and columns, which does
not change the communication complexity, $M_{g}$ is a tensor product of the
XOR function with an all ones matrix. The log rank conjecture in the case
$(f\circ\oplus^{n})(x,y)=f(x_{1}\oplus y_{1},\ldots,x_{n}\oplus y_{n})$
remains an interesting open question. Shi and Zhang [SZ09a] have recently
resolved this question when $f$ is symmetric.

##  4 A bound in terms of approximate degree

In this section, we will address the frameworks of Sherstov and Shi-Zhu. We
extend both of these frameworks to give more general conditions on the inner
function $g$ which still imply that the approximate degree of $f$ is a lower
bound on the quantum query complexity of the composed function $f\circ g^{n}$.
In outline, both of these frameworks follow the same plan. By Theorem 2.4 it
suffices to lower bound the approximate $\gamma_{2}$ norm (or even approximate
trace norm) of $f\circ g^{n}$. To do this, they use the dual formulation given
by Proposition 1 and construct a witness matrix $B$ which has non-negligible
correlation with the target function and small $\gamma_{2}^{*}$ (or spectral)
norm.

A very nice way to construct this witness, used by both Sherstov and Shi-Zhu,
is to use the dual polynomial of $f$. This is a polynomial $v$ which certifies
that the approximate polynomial degree of $f$ is at least a certain value.
More precisely, duality theory of linear programming gives the following
lemma.

######  Lemma 1 (Sherstov [She09], Shi-Zhu [SZ09b])

Let $f:\\{-1,+1\\}^{n}$ $\rightarrow\\{-1,+1\\}$ and let
$d=\deg_{\epsilon}(f)$. Then there exists a function
$v:\\{-1,+1\\}^{n}\rightarrow\mathbb{R}$ such that

  1. 1.

$\langle v,\chi_{T}\rangle=0$ for every character $\chi_{T}$ with $|T|<d$.

  2. 2.

$\|v\|_{1}=1$.

  3. 3.

$\langle v,f\rangle\geq\epsilon$.

Items (2),(3) are used to lower bound the correlation of the witness matrix
with the target matrix and to upper bound the $\ell_{1}$ norm of the witness
matrix. In the most difficult step, and where these works diverge, Item (1) is
used to upper bound the $\gamma_{2}^{*}$ (or spectral) norm of the witness
matrix.

We treat each of these frameworks separately in the next two sections.

###  4.1 Sherstov’s framework

The proof of the next theorem follows the same steps as Sherstov’s proof for
pattern matrices (Theorem 5.1 [She09]). Our main contribution is to identify
the strongly balanced condition as the key property of pattern matrices which
enables the proof to work.

###### Theorem 4.1

Let $X,Y$ be finite sets, $g:X\times Y\rightarrow\\{-1,+1\\}$ be a strongly
balanced function, and $M_{g}[x,y]=g(x,y)$ be the corresponding sign matrix.
Let $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$ be an arbitrary function. Then

$Q_{\epsilon}^{*}(f\circ
g^{n})\geq\deg_{\epsilon_{0}}(f)\log_{2}\Big{(}\frac{\sqrt{|X||Y|}}{\|M_{g}\|}\Big{)}-O(1).$

for any $\epsilon>0$ and $\epsilon_{0}>2\epsilon$.

In particular, this result means that the quantum and randomized complexities
of $f\circ g^{n}$ are polynomially related whenever $g$ is strongly balanced
and $\log\tfrac{\sqrt{\mathrm{size}(M_{g})}}{\|M_{g}\|}$ is polynomially
related to the randomized communication complexity of $g$. While the
complexity measure of $g$ used here may look strange at first, Shaltiel
[Sha03] has shown that it is closely related to the discrepancy of $g$ under
the uniform distribution, as noted above in Theorem 2.2. This theorem strictly
generalizes the case of pattern matrices, but it could still be the case that
the results of Shi-Zhu can show bounds not possible with this theorem.

######  Proof (Proof of Theorem 4.1)

Let $d=\deg_{\epsilon_{0}}(f)$ and let $v$ be a dual polynomial for $f$ with
properties as in Lemma 1. We define a witness matrix as

$B[x,y]=\frac{2^{n}}{\mathrm{size}(M_{g})^{n}}v(g(x^{1},y^{1}),\ldots,g(x^{n},y^{n}))$

Let us first lower bound the inner product $\langle M_{f\circ
g^{n}},B\rangle$. Notice that as $M_{g}$ is strongly balanced, it is in
particular balanced, and so the number of ones (or minus ones) in $M_{g}$ is
$\mathrm{size}(M_{g})/2$.

$\displaystyle\langle M_{f\circ
g^{n}},B\rangle=\frac{2^{n}}{\mathrm{size}(M_{g})^{n}}\sum_{z\in\\{-1,+1\\}^{n}}f(z)v(z)\prod_{i=1}^{n}\Big{(}\sum_{\scriptsize
x^{i},y^{i}:\atop\scriptsize g(x^{i},y^{i})=z_{i}}1\Big{)}=\langle
f,v\rangle\geq\epsilon_{0}$

A similar argument shows that $\|B\|_{1}=1$ as $\|v\|_{1}=1$.

Now we turn to evaluate $\|B\|$. As shown above, the strongly balanced
property of $g$ implies that the matrices $\chi_{T}\circ g^{n}$ and
$\chi_{S}\circ g^{n}$ are orthogonal for distinct sets
$S,T\subseteq\\{0,1\\}^{n}$. We can thus use Fact 2.1 to compute as follows.

$\displaystyle\|B\|$
$\displaystyle=\frac{2^{n}}{\mathrm{size}(M_{g})^{n}}\|\sum_{T\subseteq[n]}\hat{v}_{T}M_{\chi_{T}\circ
g^{n}}\|$
$\displaystyle=\frac{2^{n}}{\mathrm{size}(M_{g})^{n}}\max_{T}|\hat{v}_{T}|\|M_{\chi_{T}\circ
g^{n}}\|$ $\displaystyle=\max_{T}\
2^{n}|\hat{v}_{T}|\prod_{i}\frac{\|M_{g}^{T[i]}\|}{\mathrm{size}(M_{g})}$
$\displaystyle\leq\max_{T:\hat{v}_{T}\neq
0}\prod_{i}\frac{\|M_{g}^{T[i]}\|}{\mathrm{size}(M_{g})}$
$\displaystyle=\left(\frac{\|M_{g}\|}{\sqrt{\mathrm{size}(M_{g})}}\right)^{d}\left(\frac{1}{\mathrm{size}(M_{g})}\right)^{n/2}$

In the second to last step we have used that $|\hat{v}_{T}|\leq 1/2^{n}$ as
$\|v\|_{1}=1$, and in the last step we have used the fact that
$\|J\|=\sqrt{\mathrm{size}(M_{g})}$.

Now putting everything together we have

$\displaystyle\frac{\|M_{f\circ
g^{n}}\|_{tr}^{\epsilon_{0}}}{\sqrt{\mathrm{size}(M_{f\circ
g^{n}})}}\geq\frac{1}{12}\left(\frac{\sqrt{\mathrm{size}(M_{g})}}{\|M_{g}\|}\right)^{d}$

The lower bound on quantum communication complexity now follows from Theorem
2.4.

Using the theorem of Shaltiel relating discrepancy to the spectral norm
Theorem 2.2, we get the following corollary:

###### Corollary 3

Let the quantities be defined as in Theorem 4.1.

$Q_{1/8}^{*}(f\circ
g^{n})\geq\frac{1}{3}\deg_{1/3}(f)\big{(}\log\big{(}\frac{1}{\mathrm{disc}_{U}(M_{g})}\big{)}-7\big{)}-O(1).$

Comparison to Sherstov’s pattern matrix: As mentioned in [She09], Sherstov’s
pattern matrix method can prove quantum lower bound of
$\Omega(\deg_{\epsilon}(f))$ for block composed functions $f\circ g^{n}$ if
the matrix $M_{g}$ contains the following $4\times 4$ one as a submatrix:

$S_{4}=\begin{bmatrix}1&-1&1&-1\\\ 1&-1&-1&1\\\ -1&1&1&-1\\\
-1&1&-1&1\end{bmatrix}$

In this paper we show that the same lower bound holds as long as $M_{g}$
contains a strongly balanced submatrix or rank greater than one. Are there
strongly balanced matrices not containing $S_{4}$ as a submatrix? It turns out
that the answer is yes: we give the following $6\times 6$ matrix as one
example.

$S_{6}=\begin{bmatrix}1&1&1&-1&-1&-1\\\ 1&1&-1&1&-1&-1\\\ 1&-1&-1&-1&1&1\\\
-1&-1&1&1&1&-1\\\ -1&1&-1&-1&1&1\\\ -1&-1&1&1&-1&1\end{bmatrix}$

###  4.2 Shi-Zhu framework

The method of Shi-Zhu does not restrict the form of the inner function $g$,
but rather works for any $g$ which is sufficiently “hard.” The hardness
condition they require is phrased in terms of a somewhat awkward measure they
term spectral discrepancy.

######  Definition 6 (spectral discrepancy)

Let $A$ be a $m$-by-$n$ sign matrix. The spectral discrepancy of $A$, denoted
$\rho(A)$, is the smallest $r$ such that there is a submatrix $A^{\prime}$ of
$A$ and a probability distribution $\mu$ on the entries of $A^{\prime}$
satisfying:

  1. 1.

$A^{\prime}$ is balanced with respect to $\mu$, i.e. the distribution which
gives equal weight to $-1$ entries and $+1$ entries of $A^{\prime}$.

  2. 2.

The spectral norm of $A^{\prime}\bullet\mu$ is small:

$\|A^{\prime}\bullet\mu\|\leq\frac{r}{\sqrt{\mathrm{size}(A^{\prime})}}$

  3. 3.

The entrywise absolute value of the matrix $A^{\prime}\bullet\mu$ should also
have a bound on its spectral norm in terms of $r$:

$\||A^{\prime}\bullet\mu|\|\leq\frac{1+r}{\sqrt{\mathrm{size}(A^{\prime})}}$

While conditions (1),(2) in the definition of spectral discrepancy are quite
natural, condition (3) can be complicated to verify. Note that condition (3)
will always be satisfied when $\mu$ is taken to be the uniform distribution.
Using this notion of spectral discrepancy, Shi-Zhu show the following theorem.

######  Theorem 4.2 (Shi-Zhu [SZ09b])

Let $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$, and $g:X\times
Y\rightarrow\\{-1,+1\\}$. For any $\epsilon$ and $\epsilon_{0}>2\epsilon$,

$Q_{\epsilon}(f\circ g^{n})\geq\Omega(\deg_{\epsilon_{0}}(f)).$

provided $\rho(M_{g})\leq\tfrac{\deg_{\epsilon_{0}}(f)}{2en}$. Here
$e=2.718\ldots$ is Euler’s number.

Chattopadhyay [Cha08] extended the technique of Shi-Zhu to the case of
multiparty communication complexity, answering an open question of Sherstov
[She08a]. In doing so, he gave a more natural condition on the hardness of $g$
in terms of an upper bound on discrepancy frequently used in the multiparty
setting and originally due to Babai, Nisan, and Szegedy [BNS92]. As all that
is crucially needed is subadditivity, we do the argument here with
$\gamma_{2}^{*}$, which is essentially equal to the discrepancy.

###### Theorem 4.3

Let $f:\\{-1,+1\\}^{n}\rightarrow\\{-1,+1\\}$, and $g:X\times
Y\rightarrow\\{-1,+1\\}$. Fix $0<\epsilon<1/2$, and let
$\epsilon_{0}>2\epsilon$. Then

$Q_{\epsilon}^{*}(f\circ g^{n})\geq\deg_{\epsilon_{0}}(f)-O(1).$

provided there is a distribution $\mu$ which is balanced with respect to $g$
and for which
$\gamma_{2}^{*}(M_{g}\bullet\mu)\leq\tfrac{\deg_{\epsilon_{0}}(f)}{2en}$.

###### Proof

We again use Proposition 1, this time with the $\gamma_{2}$ norm instead of
the trace norm.

$\gamma_{2}^{\epsilon_{0}}(M_{f\circ g^{n}})=\max_{B}\frac{\langle M_{f\circ
g^{n}},B\rangle-\epsilon_{0}\|B\|_{1}}{\gamma_{2}^{*}(B)}.$

To prove a lower bound we choose a witness matrix $B$ as follows

$B[x,y]=2^{n}\cdot
v(g(x^{1},y^{1}),\ldots,g(x^{n},y^{n}))\cdot\prod_{i=1}^{n}\mu(x^{i},y^{i}).$

where $v$ witnesses that $f$ has approximate degree at least
$d=\deg_{\epsilon_{0}}(f)$. This definition is the same as in the previous
section where $\mu$ was simply the uniform distribution. As argued before, we
have $\langle M_{f\circ g^{n}},B\rangle\geq\epsilon_{0}$ and $\|B\|_{1}=1$
because $M_{g}\bullet\mu$ is balanced.

We again expand $B$ as

$B=2^{n}\sum_{T:|T|\geq
d}\hat{v}_{T}\bigotimes_{i=1}^{n}(M_{g}\bullet\mu)^{T(i)},$

where $(M_{g}\bullet\mu)^{1}=M_{g}\bullet\mu$ and $(M_{g}\bullet\mu)^{0}=\mu$.

Now comes the difference with the previous proof. As we do not have special
knowledge of the function $g$, we simply bound $\gamma_{2}^{*}(B)$ using the
triangle inequality.

$\displaystyle\gamma_{2}^{*}(B)$ $\displaystyle\leq 2^{n}\sum_{T:|T|\geq
d}|\hat{v}_{T}|\
\gamma_{2}^{*}\left(\bigotimes_{i=1}^{n}(M_{g}\bullet\mu)^{T(i)}\right)$
$\displaystyle=2^{n}\sum_{T:|T|\geq d}|\hat{v}_{T}|\
\gamma_{2}^{*}(M_{g}\bullet\mu)^{|T|}\gamma_{2}^{*}(\mu)^{n-|T|}$
$\displaystyle\leq\sum_{T:|T|\geq d}\gamma_{2}^{*}(M_{g}\bullet\mu)^{|T|},$

where in the last step we have used that $\gamma_{2}^{*}(\mu)\leq 1$ as $\mu$
is a probability distribution and that $|\hat{v}_{T}|\leq 2^{-n}$. In the
second step (equality) we used the fact that $\gamma_{2}^{*}$ is
multiplicative with respect to tensor product, a property proved in [LSŠ08].
We continue with simple arithmetic:

$\displaystyle\gamma_{2}^{*}(B)$ $\displaystyle\leq\sum_{i=d}^{n}{n\choose
i}\gamma_{2}^{*}(M_{g}\bullet\mu)^{i}$
$\displaystyle\leq\sum_{i=d}^{n}\left(\frac{en\gamma_{2}^{*}(M_{g}\bullet\mu)}{d}\right)^{i}$
$\displaystyle\leq 2^{-d}$

provided that $\gamma_{2}^{*}(M_{g}\bullet\mu)\leq\frac{d}{2en}$.

##  5 A general framework for functions composed through a group

In this section we begin the study of more general function composition
through a group $G$. In this case the outer function
$f:G\rightarrow\\{-1,+1\\}$ is a class function, i.e. invariant on conjugacy
classes, and the inner function $g:X\times Y\to G$ has range $G$. We define
the composed function as $F(x,y)=f(g(x,y))$. In previous sections of the paper
we have just dealt with the case $G=\mathbb{Z}_{2}^{n}$.

Let us recall the basic idea of the proof of Theorem 4.1. To prove a lower
bound on the quantum communication complexity for a composed function $f\circ
g$, we constructed a witness matrix $B$ which had non-negligible correlation
with $f\circ g$ and small spectral norm. To do this, following the work of
Sherstov and Shi-Zhu [She09, SZ09b], we considered the dual polynomial $p$ of
$f$ using LP duality. The dual polynomial has two important properties, first
that $p$ has non-negligible correlation with $f$ and second that $p$ has no
support on low degree polynomials. We can then use the first property to show
that the composed function $p\circ g$ will give non-negligible inner product
with $f\circ g$ and the second to upper bound the spectral norm of $p\circ g$.
The second of these tasks is the more difficult. In the case of
$G=\\{-1,+1\\}^{n}$, the degree of a character $\chi_{T}$ is a natural measure
of how “hard” the character is — the larger $T$ is, the smaller the spectral
norm of $\chi_{T}\circ g$ will be. In the general group case, however, it is
less clear what the corresponding “hard” and “easy” characters should be. In
Section 5.1, we will show that this framework actually works for an arbitrary
partition of the basis functions into Easy and Hard. That is for any arbitrary
partition of the basis functions into Easy and Hard sets we can follow the
plan outlined above and look for a function with support on the Hard set which
has non-negligible correlation with $f$.

In carrying out this plan, one is still left with upper bounding $\|M_{p\circ
g}\|$. Here, as in the Boolean case, it as again very convenient to have an
orthogonality condition which can greatly simplify the computation of
$\|M_{p\circ g}\|$ and give good bounds. In the Boolean case we have shown
that $M_{g}$ being strongly balanced implies this key orthogonality condition.
In Section 5.2 and 5.3, we will show that for the general group, the condition
is not only about each row and column of matrix $M_{g}$, but all pairs of rows
and pairs of columns. In the Abelian group case, this reduces to a nice group
invariance condition.

Even after applying the orthogonality condition to use the maximum bound
instead of the triangle inequality for $\|M_{p\circ g}\|$, the remaining term
$\|M_{\chi_{i}\circ g}\|$ (where $\chi_{i}$ is a “hard” character) is still
not easy to upper bound. For block composed functions, fortunately, the tensor
structure makes it feasible to compute. Section 5.4 gives a generalized
version of Theorem 4.1.

###  5.1 General framework

For a multiset $T$, $x\in T$ means $x$ running over $T$. Thus $T=\\{a(s):s\in
S\\}$ means the multiset formed by collecting $a(s)$ with $s$ running over
$S$.

For a set $S$, denote by $L_{\mathbb{C}}(S)$ the $|S|$-dimensional vector
space over the field $\mathbb{C}$ (of complex numbers) consisting of all
linear functions from $S$ to $\mathbb{C}$, endowed with inner product
$\langle\psi,\phi\rangle=\frac{1}{|S|}\sum_{s\in S}\psi(s)\overline{\phi(s)}$.
The distance of a function $f\in L_{\mathbb{C}}(S)$ to a subspace $\Phi$ of
$L_{\mathbb{C}}(S)$, denoted by $d(f,\Phi)$, is defined as
$\min\\{\delta:\|f^{\prime}-f\|_{\infty}\leq\delta,f^{\prime}\in\Phi\\}$, i.e.
the magnitude of the least entrywise perturbation to turn $f$ into $\Phi$.

In the above setting, Theorem 4.1 generalizes to the following.

###### Theorem 5.1

Consider a sign matrix $A=[f(g(x,y))]_{x,y}$ where $g:X\times Y\rightarrow S$
for a set $S$, and $f:S\rightarrow\\{-1,+1\\}$. Suppose that we can find an
orthogonal basis functions $\Psi=\\{\psi_{i}:i\in[|S|]\\}$ for
$L_{\mathbb{C}}(S)$. For any hardness partition
$\Psi=\Psi_{Hard}\uplus\Psi_{Easy}$, let $\delta=d(f,span(\Psi_{Easy}))$. If

  1. 1.

(regularity) The multiset $\\{g(x,y):x\in X,y\in Y\\}$ is a multiple of $S$,
i.e. $S$ repeated for some number of times.

  2. 2.

(orthogonality) for all $x,x^{\prime},y,y^{\prime}$ and all distinct
$\psi_{i},\psi_{j}\in\Psi_{Hard}$,

$\displaystyle\sum_{y}\psi_{i}(g(x,y))\overline{\psi_{j}(g(x^{\prime},y))}=\sum_{x}\psi_{i}(g(x,y))\overline{\psi_{j}(g(x,y^{\prime}))}=0,$

then

$\displaystyle
Q_{\epsilon}(A)\geq\log_{2}\frac{\sqrt{MN}\cdot(\delta-2\epsilon)}{\max_{\psi_{i}\in\Psi_{Hard}}(\max_{g}|\psi_{i}(g)|\cdot\|[\psi_{i}(g(x,y))]_{x,y}\|)}-O(1).$

Using the idea of finding a certificate of the high approximate degree by
duality [She09, SZ09b], we have the following fact analogous to Lemma 1.

###### Lemma 2

For a function $f:S\rightarrow\mbox{$\mathbb{C}$}$ and a subspace $\Phi$ of
$L_{\mathbb{C}}(S)$, if $d(f,span(\Phi))=\delta$, then there exists a function
$h$ s.t.

$\displaystyle\hat{h}_{i}=0,\ \forall\psi_{i}\in\Phi$ (1)
$\displaystyle\sum_{g\in G}|h(g)|\leq 2,$ (2) $\displaystyle|\sum_{g\in
G}f(g)\overline{h(g)}|>\delta$ (3)

Using the lemma, we can prove the Theorem 5.1.

###### Proof

(of Theorem 5.1) By the regularity property, we know that when $(x,y)$ runs
over $X\times Y$, $g(x,y)$ runs over $S$ exactly $K$ times where $K=MN/|G|$.
Consider $B=\frac{1}{K}[h(g(x,y))]_{x,y}$, $h$ obtained by Lemma 2; we want to
apply Proposition 1 and Theorem 2.4 by using this $B$. First,

$\|B\|_{1}=\frac{1}{K}\sum_{x,y}|h(g(x,y))|=\sum_{g\in G}|h(g)|\leq 1.$ (4)

Also,

$\displaystyle|\langle A,B\rangle|$
$\displaystyle=\frac{1}{K}|\sum_{x,y}f(g(x,y))\overline{h(g(x,y))}|$
$\displaystyle=|\sum_{g\in G}f(g)\overline{h(g)}|>\delta$

Now we need to compute

$\|B\|=\frac{1}{K}\big{\|}[\sum_{\chi_{i}\in
Hard}\hat{h}_{i}\chi_{i}(g(x,y))]_{x,y}\big{\|}.$

Note that

$\displaystyle[\psi_{i}(g(x,y))]_{x,y}^{\dagger}[\psi_{j}(g(x,y))]_{x,y}=[\sum_{x}\overline{\psi_{i}(g(x,y))}\psi_{j}(g(x,y^{\prime}))]_{y,y^{\prime}}$

and

$\displaystyle[\psi_{i}(g(x,y))]_{x,y}[\psi_{j}(g(x,y))]_{x,y}^{\dagger}=[\sum_{y}\psi_{i}(g(x,y))\overline{\psi_{j}(g(x^{\prime},y))}]_{x,x^{\prime}}.$

Thus the orthogonality condition implies that

$\displaystyle[\psi_{i}(g(x,y))]_{x,y}^{\dagger}[\psi_{j}(g(x,y))]_{x,y}=[\psi_{i}(g(x,y))]_{x,y}[\psi_{j}(g(x,y))]_{x,y}^{\dagger}=0$

for all $i\neq j$. Now as in [She09], we can use the max bound

$\displaystyle\|B\|$
$\displaystyle=\frac{1}{K}\max_{i:\psi_{i}\in\Psi_{Hard}}\big{\|}\hat{h}_{i}[\psi_{i}(x,y)]_{x,y}\big{\|}$
$\displaystyle\leq\frac{1}{K}\max_{i:\psi_{i}\in
Hard}|\hat{h}_{i}|\max_{\psi_{i}\in
Hard}\big{\|}[\psi_{i}(x,y)]_{x,y}\big{\|}$
$\displaystyle\leq\frac{1}{K|G|}\max_{\psi_{i}\in
Hard}\big{(}\max_{g}|\psi_{i}(g)|\cdot\big{\|}[\psi_{i}(x,y)]_{x,y}\big{\|}\big{)}.$

where the last inequality is due to Eq. (5) and Eq. (4). Finally note
$K|G|=MN$ to complete the proof.

In the Boolean block composed function case, the regularity condition reduces
to the matrix $[g(x,y)]$ being balanced, and later we will prove that the
orthogonality condition reduces to the strongly balanced property. From this
theorem we can see that the way to partition $\Psi$ into $\Psi_{Easy}$ and
$\Psi_{Hard}$ does not really matter for the lower bound proof passing
through. However, the partition does play a role when we later bound the
spectral norm in the denominator.

###  5.2 Functions with group symmetry

For a general finite group $G$, two elements $s$ and $t$ are conjugate,
denoted by $s\sim t$, if there exists an element $r\in G$ s.t. $rsr^{-1}=t$.
Define $H$ as the set of all class functions, i.e. functions $f$ s.t.
$f(s)=f(t)$ if $s\sim t$. Then $H$ is an $h$-dimensional subspace of
$L_{\mathbb{C}}(G)$, where $h$ is the number of conjugacy classes. The
irreducible characters $\\{\chi_{i}:i\in[h]\\}$ form an orthogonal basis of
$H$. For a class function $f$ and irreducible characters $\chi_{i}$, denote by
$\hat{f}_{i}$ the coefficient of $\chi_{i}$ in expansion of $f$ according to
$\chi_{i}$’s, i.e.
$\hat{f}_{i}=\langle\chi_{i},f\rangle=\frac{1}{|G|}\sum_{g\in
G}\chi_{i}(g)\overline{f(g)}$. An easy fact is that for any $i$, we have

$\displaystyle|\hat{f}_{i}|$ $\displaystyle=\frac{1}{|G|}\left|\sum_{g\in
G}\chi_{i}(g)\overline{f(g)}\right|\leq\frac{1}{|G|}\sum_{g\in
G}|f(g)||\chi_{i}(g)|\leq\Big{(}\frac{1}{|G|}\sum_{g\in
G}|f(g)|\Big{)}\cdot\max_{g}|\chi_{i}(g)|.$ (5)

If $G$ is Abelian, then it always has $|\chi_{i}(g)|=1$, thus
$\max_{i}|\hat{f}_{i}|\leq\frac{1}{|G|}\sum_{g\in G}|f(g)|$. For general
groups, we have $|\chi_{i}(g)|\leq\deg(\chi_{i})$, where $\deg(\chi_{i})$ is
the degree of $\chi_{i}$, namely the dimension of the associated vector space.

In this section we consider the setting that $S$ is a finite group $G$. The
goal is to exploit properties of group characters to give better form of the
lower bound. In particular, we hope to see when the second condition holds and
what the matrix operator norm $\|[\psi_{(}g(x,y))]_{x,y}\|$ is in this
setting.

The standard orthogonality of irreducible characters says that $\sum_{s\in
G}\chi_{i}(s)\overline{\chi_{j}(s)}=0$. The second condition in Theorem 5.1 is
concerned with a more general case: For a multiset $T$ with elements in
$G\times G$, we need

$\sum_{(s,t)\in T}\chi_{i}(s)\overline{\chi_{j}(t)}=0,\qquad\forall i\neq j.$
(6)

The standard orthogonality relation corresponds to the special that
$T=\\{(s,s):s\in G\\}$. We hope to have a characterization of a multiset $T$
to make Eq. (6) hold.

We may think of the a multiset $T$ with elements in set $S$ as a function on
$S$, with the value on $s\in S$ being the multiplicity of $s$ in $T$. Since
characters are class functions, for each pair $(C_{k},C_{l})$ of conjugacy
classes, only the value $\sum_{g_{1}\in C_{k},t\in C_{l}}T(g_{1},t)$ matters
for the sake of Eq. (6). We thus make $T$ a class function by taking average
within each class pair $(C_{k},C_{l})$. That is, define a new function
$T^{\prime}$ as

$T^{\prime}(s,t)=\sum_{s\in C_{k},t\in C_{l}}T(s,t)/(|C_{k}||C_{l}|),\ \forall
s\in C_{k},\ \forall t\in C_{l}.$

###### Proposition 2

For a finite group $G$ and a multiset $T$ with elements in $G\times G$, the
following three statements are equivalent:

  1. 1.

$\sum_{(s,t)\in T}\chi_{i}(s)\overline{\chi_{j}(t)}=0,\ \forall i\neq j$

  2. 2.

$T^{\prime}$, as a function, is in
$span\\{\chi_{i}\otimes\overline{\chi_{i}}:i\in[h]\\}$

  3. 3.

$[T^{\prime}(s,t)]_{s,t}=C^{\dagger}DC$ where $D$ is a diagonal matrix and
$C=[\chi_{i}(s)]_{i,s}$. That is, $T^{\prime}$, as a matrix, is normal and
diagonalized exactly by the irreducible characters.

###### Proof

Let $H_{2}$ be the subspace consisting functions $f:G\times
G\rightarrow\mbox{$\mathbb{C}$}$ s.t. $f(s,t)=f(s^{\prime},t^{\prime})$ if
$s\sim s^{\prime}$, $t\sim t^{\prime}$. Note that for direct product group
$G\times G$, $\\{\chi_{i}\otimes\overline{\chi_{j}}:i,j\\}$ form an orthogonal
basis of $H_{2}$:

$\displaystyle\sum_{s,t\in
G}\chi_{i}(s)\overline{\chi_{j}(t)}\overline{\chi_{i^{\prime}}(s)\overline{\chi_{j^{\prime}}(t)}}=\big{(}\sum_{s\in
G}\chi_{i}(s)\overline{\chi_{i^{\prime}}(s)}\big{)}\big{(}\sum_{t\in
G}\overline{\chi_{j}(t)}\chi_{j^{\prime}}(t)\big{)}=0$

unless $i=i^{\prime}$ and $j=j^{\prime}$. Note that by viewing $T$ as a
function from $G\times G$ to $\mathbb{C}$, the Eq. (6) and the definition of
$T^{\prime}$ imply that

$\langle\chi_{i}\otimes\overline{\chi_{j}},\ T\rangle=0,\forall i\neq j$

Thus the first two statements are equivalent.

Note that

$\displaystyle T^{\prime}\in
span\\{\chi_{i}\otimes\overline{\chi_{i}}:i\in[h]\\}\quad\Leftrightarrow\quad
T^{\prime}(s,t)=\sum_{i}\alpha_{i}\chi_{i}(s)\overline{\chi_{i}(t)}\quad\text{
for some $\alpha_{i}$'s}$

Denote by $C_{h\times|G|}=[\chi_{i}(g)]_{i,g}$ the matrix of the character
table. Then observe that the summation in the last equality is nothing but the
$(s,t)$ entry of the matrix $C^{\dagger}diag(\alpha_{1},\cdots,\alpha_{h})C$.
Therefore the equivalence of the second and third statements follows.

###  5.3 Abelian group

When $G$ is Abelian, we have further properties to use. The first one is that
$|\chi_{i}(g)|=1$ for all $i$. The second one is that the irreducible
characters are homomorphisms of $G$; that is,
$\chi_{i}(st)=\chi_{i}(s)\chi_{i}(t)$. This gives a clean characterization of
the orthogonality condition by group invariance. For a multiset $T$, denote by
$sT$ another multiset obtained by collecting all $st$ where $t$ runs over $T$.
A multiset $T$ with elements in $G\times G$ is _$G$ invariant_ if it satisfies
$(g,g)T=T$ for all $g\in G$. We can also call a function $T:G\times
G\rightarrow\mbox{$\mathbb{C}$}$ $G$ invariant if $T(s,t)=T(rs,rt)$ for all
$r,s,t\in G$. The overloading of the name is consistent when we view a
multiset $T$ as a function (counting the multiplicity of elements).

###### Proposition 3

For a finite Abelian group $G$ and a multiset $T$ with elements in $G\times
G$,

$\text{$T$ is $G$ invariant}\Leftrightarrow\sum_{(s,t)\in
T}\chi_{i}(s)\overline{\chi_{j}(t)}=0,\quad\forall i\neq j.$ (7)

###### Proof

$\Rightarrow$: Since $T$ is $G$ invariant, $T=(r,r)T$ and thus,

$\displaystyle\sum_{(s,t)\in T}\chi_{i}(s)\overline{\chi_{j}(t)}$
$\displaystyle=\sum_{(s,t)\in(r,r)T}\chi_{i}(s)\overline{\chi_{j}(t)}$ (8)
$\displaystyle=\sum_{(s^{\prime},t^{\prime})\in
T}\chi_{i}(rs^{\prime})\overline{\chi_{j}(rt^{\prime})}$ (9)

Now using the fact that irreducible characters of Abelian groups are
homomorphisms, we have

$\displaystyle\sum_{(s^{\prime},t^{\prime})\in
T}\chi_{i}(rs^{\prime})\overline{\chi_{j}(rt^{\prime})}=$
$\displaystyle\sum_{(s^{\prime},t^{\prime})\in
T}\chi_{i}(r)\chi_{i}(s^{\prime})\overline{\chi_{j}(r)}\overline{\chi_{j}(t^{\prime})}$
$\displaystyle=$
$\displaystyle\chi_{i}(r)\overline{\chi_{j}(r)}\Big{(}\sum_{(s^{\prime},t^{\prime})\in
T}\chi_{i}(s^{\prime})\overline{\chi_{j}(t^{\prime})}\Big{)}$

But note that this holds for any $r\in G$, thus also for the average of them.
That is,

$\displaystyle\sum_{(s,t)\in T}\chi_{i}(s)\overline{\chi_{j}(t)}=$
$\displaystyle\frac{1}{|G|}\Big{(}\sum_{r\in
G}\chi_{i}(r)\overline{\chi_{j}(r)}\Big{)}\Big{(}\sum_{(s^{\prime},t^{\prime})\in
T}\chi_{i}(s^{\prime})\overline{\chi_{j}(t^{\prime})}\Big{)}=0,$

by the standard orthogonality property of different irreducible characters.

$\Leftarrow$: Since $\sum_{(s,t)\in T}\chi_{i}(s)\overline{\chi_{j}(t)}=0$,
$\forall i\neq j$, we know that $T$ as a function is in
$span\\{\chi_{i}\otimes\overline{\chi_{i}}:i\\}$. Note that any linear
combination of $G$ invariant functions is also $G$ invariant. Thus it remains
to check that each basis $\chi_{i}\otimes\overline{\chi_{i}}$ is $G$
invariant, which is easy to see:

$\chi_{i}(rs)\overline{\chi_{i}(rt)}=\chi_{i}(r)\chi_{i}(s)\overline{\chi_{i}(r)}\overline{\chi_{i}(t)}=\chi_{i}(s)\overline{\chi_{i}(t)}.$

This finishes the proof.

Another nice property of Abelian groups is that the orthogonality condition
condition implies the regularity one.

###### Proposition 4

For an Abelian group $G$, if either $T^{y,y}$ is $G$ invariant for all $y$ or
$S^{x,x}$ is $G$ invariant for all $x$, then $G|\\{g(x,y):x\in X,y\in Y\\}$.

###### Proof

Note that $T^{y,y}(s,s)=|\\{x:g(x,y)=s\\}|$, thus $T^{y,y}$ being $G$
invariant implies that $|\\{x:g(x,y)=s\\}|=|\\{x:g(x,y)=t\\}|$ for all $s,t\in
G$. Thus the column $y$ in matrix $[g(x,y)]_{x,y}$, when viewed as a multiset,
is equal to $G$ repeated $|Y|/|G|$ times. Therefore the whole multiset
$\\{g(x,y):x\in X,y\in Y\\}$ is a multiple of $G$ as well.

What we finally get for Abelian groups is the following.

###### Corollary 4

For a sign matrix $A=[f(g(x,y))]_{x,y}$ and an Abelian group $G$, if
$d(f,span(Ch_{Easy}))=\Omega(1)$, and the multisets
$S^{x,x^{\prime}}=\\{(g(x,y),g(x^{\prime},y)):y\in Y\\}$ and
$T^{y,y^{\prime}}=\\{(g(x,y),g(x,y^{\prime})):x\in X\\}$ are $G$ invariant for
any $(x,x^{\prime})$ and any $(y,y^{\prime})$, then

$Q(A)\geq\log_{2}\frac{\sqrt{MN}}{\max_{i\in
Hard}\|[\chi_{i}(g(x,y))]_{x,y}\|}-O(1).$

###  5.4 Block composed functions

We now consider a special class of functions $g$: block composed functions.
Suppose the group $G$ is a product group $G=G_{1}\times\cdots\times G_{t}$,
and $g(x,y)=(g_{1}(x^{1},y^{1}),\cdots,g_{t}(x^{t},y^{t}))$ where
$x=(x^{1},\cdots,x^{t})$ and $y=(y^{1},\cdots,y^{t})$. That is, both $x$ and
$y$ are decomposed into $t$ components and the $i$-th coordinate of $g(x,y)$
only depends on the $i$-th components of $x$ and $y$. The tensor structure
makes all the computation easy. Theorem 4.1 can be generalized to the general
product group case for arbitrary groups $G_{i}$.

###### Definition 7

The $\epsilon$-approximate degree of a class function $f$ on product group
$G_{1}\times\cdots\times G_{t}$, denoted by $d_{\epsilon}(f)$, is the minimum
$d$ s.t. $\|f-f^{\prime}\|_{\infty}\leq\epsilon$, where $f^{\prime}$ can be
represented as a linear combination of irreducible characters with at most $d$
non-identity component characters.

###### Theorem 5.2

For sign matrix

$A=[f(g_{1}(x^{1},y^{1}),\cdots,g_{t}(x^{t},y^{t})]_{x,y}$

where all $g_{i}$ satisfy their orthogonality conditions, we have

$Q(A)\geq\min_{\\{\chi_{i}\\},S}\sum_{i\in
S}\log_{2}\frac{\sqrt{\mathrm{size}(M_{g_{i}})}}{\deg(\chi_{i})\|M_{\chi_{i}\circ
g_{i}}\|}-O(1)$

where the minimum is over all $S\subseteq[n]$ with $|S|>\deg_{1/3}(f)$, and
all non-identity irreducible characters $\chi_{i}$ of $G_{i}$.

###### Proof

Recall that an irreducible character $\chi$ of $G$ is the tensor product of
irreducible characters $\chi_{i}$ of each component group $G_{i}$. Let Hard be
the set of irreducible characters $\chi$ with more than $d$ non-identity
component characters. Fix a hard character $\chi$, and denote by $S$ the set
of coordinates of its non-identity characters.

$\displaystyle\|[\chi(g(x,y))]\|$
$\displaystyle=\|\bigotimes_{i\in[t]}[\chi_{i}(g_{i}(x^{i},y^{i}))]\|$
$\displaystyle=\prod_{i\in[t]}\|[\chi_{i}(g_{i}(x^{i},y^{i}))]\|$
$\displaystyle=\prod_{i\in
S}\|[\chi_{i}(g_{i}(x^{i},y^{i}))]\|\times\prod_{i\notin
S}\|J_{|X_{i}|\times|Y_{i}|}\|$ $\displaystyle=\prod_{i\in
S}\|M_{\chi_{i}\circ g_{i}}\|\times\prod_{i\notin
S}\sqrt{\mathrm{size}(M_{g_{i}})}$

Thus by Theorem 5.1 and Eq. (5), we have

$\displaystyle Q(A)\geq\log_{2}\prod_{i\in
S}\frac{\sqrt{\mathrm{size}(M_{g_{i}})}}{\deg(\chi_{i})\cdot\|M_{\chi_{i}\circ
g_{i}}\|}-O(1)$ (10)

proving the theorem.

Previous sections as well as [SZ09b] consider the case where all $g_{i}$’s are
the same and all $G_{i}$’s are $\mbox{$\mathbb{Z}$}_{2}$. In this case, the
above bound is equal to the one in Theorem 4.1, and the following proposition
says that the group invariance condition degenerates to the strongly balanced
property.

###### Proposition 5

For $G=\mbox{$\mathbb{Z}$}_{2}^{\times t}$, the following two conditions for
$g=(g_{1},\cdots,g_{t})$ are equivalent:

  1. 1.

The multisets $S^{x,x^{\prime}}=\\{(g(x,y),g(x^{\prime},y)):y\in Y\\}$ and
$T^{y,y^{\prime}}=\\{(g(x,y),g(x,y^{\prime})):x\in X\\}$ are $G$ invariant for
any $(x,x^{\prime})$ and any $(y,y^{\prime})$,

  2. 2.

Each matrix $[g_{i}(x^{i},y^{i})]_{x^{i},y^{i}}$ is strongly balanced.

###### Proof

1 $\Rightarrow$ 2: $S^{x,x^{\prime}}$ being $G$ invariant implies that for all
$\\{z_{i}\\},\\{u_{i}\\},\\{v_{i}\\}$,

$\displaystyle|\\{y:z_{i}g_{i}(x^{i},y^{i})=u_{i},\ z_{i}g_{i}(x^{\prime
i},y^{i})=v_{i},\forall i\\}|$ $\displaystyle=$
$\displaystyle|\\{y:g_{i}(x^{i},y^{i})=u_{i},\ g_{i}(x^{\prime
i},y^{i})=v_{i},\forall i\\}|.$

Take $x^{\prime}=x$ and $u=v$. Now for each $i$ and each row $x^{i}$, take
$z_{i}=-1$ (where the group $\mbox{$\mathbb{Z}$}_{2}$ is represented by
$\\{\pm 1\\}$). For all other $i^{\prime}\neq i$, take $z_{i^{\prime}}=1$.
This assignment will show that

$|\\{y:g_{i}(x^{i},y^{i})=-u_{i}\\}|=|\\{y:g_{i}(x^{i},y^{i})=u_{i}\\}|.$

That is, the row $x^{i}$ in matrix $[g_{i}(x^{i},y^{i})]$ is balanced.
Similarly we can show the balance for each column.

2 $\Rightarrow$ 1: It is enough to show that for each $i$ and each
$\\{z_{i}\\},\\{u_{i}\\},\\{v_{i}\\}$,

$\displaystyle|\\{y^{i}:z_{i}g_{i}(x^{i},y^{i})=u_{i},\ z_{i}g_{i}(x^{\prime
i},y^{i})=v_{i}\\}|$ $\displaystyle=$
$\displaystyle|\\{y^{i}:g_{i}(x^{i},y^{i})=u_{i},\ g_{i}(x^{\prime
i},y^{i})=v_{i}\\}|.$

First consider the case $x^{\prime i}=x^{i}$. If $u_{i}\neq v_{i}$ then both
numbers are 0; if $u_{i}=v_{i}$ then both numbers are $|\\{y^{i}\\}|/2$ by the
balance of row $x^{i}$. Now assume $x^{\prime i}\neq x^{i}$. Denote
$a_{bb^{\prime}}=|\\{y^{i}:g_{i}(x^{i},y^{i})=b,\
g_{i}(x^{i},y^{i})=b^{\prime}\\}|$, then the above requirement amounts to
$a_{00}=a_{11}$ and $a_{01}=a_{10}$.

Note that we have

$\displaystyle a_{00}+a_{01}$
$\displaystyle=|\\{y^{i}:g_{i}(x^{i},y^{i})=0\\}|=|\\{y^{i}:g_{i}(x^{i},y^{i})=1\\}|=a_{10}+a_{11}$

where the second equality is due to the balance of row $x^{i}$. And similarly
we have $a_{00}+a_{10}=a_{01}+a_{11}$ by balance of row $x^{\prime i}$.
Combining the two, we get $a_{00}=a_{11}$ and $a_{01}=a_{10}$ as desired.

It is worth noting that the conclusion does not hold if any group $G_{i}$ with
size larger than two. We omit the counterexamples here.

## References

  * [BBC+01] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM, 48(4):778–797, 2001.  Earlier version in FOCS’98.
  * [BCW98] H. Buhrman, R. Cleve, and A. Wigderson.  Quantum vs. classical communication and computation.  In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 63–68, 1998.
  * [BHN09] P. Beame and D. Huynh-Ngoc.  Multiparty communication complexity and threshold circuit size of $\mathrm{AC}^{0}$.  In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, pages 53–62, 2009.
  * [BNS92] L. Babai, N. Nisan, and M. Szegedy.  Multiparty protocols, pseudorandom generators for Logspace, and time-space trade-offs.  Journal of Computer and System Sciences, 45:204–232, 1992.
  * [BW02] H. Buhrman and R. de Wolf.  Complexity measures and decision tree complexity: A survey.  Theoretical Computer Science, 288:21–43, 2002.
  * [CA08] A. Chattopadhyay and A. Ada.  Multiparty communication complexity of disjointness.  Technical Report TR-08-002, ECCC, 2008.
  * [Cha07] A. Chattopadhyay.  Discrepancy and the power of bottom fan-in depth-three circuits.  In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 449–458, 2007.
  * [Cha08] A. Chattopadhyay.  PhD thesis, McGill University, 2008.
  * [KN97] E. Kushilevitz and N. Nisan.  Communication Complexity.  Cambridge University Press, 1997.
  * [LMSS07] N. Linial, S. Mendelson, G. Schechtman, and A. Shraibman.  Complexity measures of sign matrices.  Combinatorica, 27(4):439–463, 2007.
  * [LS88] L. Lovász and M. Saks.  Möbius functions and communication complexity.  In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 81–90, 1988.
  * [LS09a] T. Lee and A. Shraibman.  Disjointness is hard in the multiparty number-on-the-forehead model.  Computational Complexity, 18(2):309–336, 2009.
  * [LS09b] T. Lee and A. Shraibman.  Lower bounds in communication complexity.  Foundations and Trends in Theoretical Computer Science, 3, 2009\.
  * [LS09c] N. Linial and A. Shraibman.  Learning complexity versus communication complexity.  Combinatorics, Probability, and Computing, 18:227–245, 2009.
  * [LS09d] N. Linial and A. Shraibman.  Lower bounds in communication complexity based on factorization norms.  Random Structures and Algorithms, 34:368–394, 2009.
  * [LSŠ08] T. Lee, A. Shraibman, and R. Špalek.  A direct product theorem for discrepancy.  In Proceedings of the 23rd IEEE Conference on Computational Complexity, pages 71–80. IEEE, 2008.
  * [Nis94] Noam Nisan.  The communication complexity of threshold gates.  In In Proceedings of Combinatorics, Paul Erdos is Eighty, pages 301–315, 1994.
  * [NS94] N. Nisan and M. Szegedy.  On the degree of Boolean functions as real polynomials.  Computational Complexity, 4:301–313, 1994.
  * [Raz99] R. Raz.  Exponential separation of quantum and classical communication complexity.  In Proceedings of the 31st ACM Symposium on the Theory of Computing, pages 358–367, 1999.
  * [Raz03] A. Razborov.  Quantum communication complexity of symmetric predicates.  Izvestiya: Mathematics, 67(1):145–159, 2003.
  * [RS08] A. Razborov and A. Sherstov.  The sign rank of $\mathrm{AC}^{0}$.  In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, pages 57–66, 2008.
  * [Sha03] R. Shaltiel.  Towards proving strong direct product theorems.  Computational Complexity, 12(1–2):1–22, 2003.
  * [She07] A. Sherstov.  Separating $\mathrm{AC}^{0}$ from depth-2 majority circuits.  In Proceedings of the 39th ACM Symposium on the Theory of Computing, pages 294–301. ACM, 2007.
  * [She08a] A. Sherstov.  Communication lower bounds using dual polynomials.  Bulletin of the EATCS, 95:59–93, 2008.
  * [She08b] A. Sherstov.  The unbounded-error communication complexity of symmetric functions.  In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, 2008.
  * [She09] A. Sherstov.  The pattern matrix method.  SIAM Journal on Computing, 2009.
  * [She10] A. Sherstov.  On quantum-classical equivalence for composed communication problems.  Quantum Information and Computation, 10(5-6):435–455, 2010.
  * [SZ09a] Y. Shi and Z. Zhang.  Communication complexities of XOR functions.  Quantum information and computation, 9(3-4):255–263, 2009.
  * [SZ09b] Y. Shi and Y. Zhu.  Quantum communication complexity of block-composed functions.  Quantum information and computation, 9(5,6):444–460, 2009.
  * [Yao79] A. Yao.  Some complexity questions related to distributive computing.  In Proceedings of the 11th ACM Symposium on the Theory of Computing, pages 209–213, 1979.
  * [Zha09] S. Zhang.  On the tightness of the Buhrman-Cleve-Wigderson simulation.  In Proceedings of the 20th International Symposium on Algorithms and Computation, pages 434–440, 2009.