Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lectures 12-13, Scribe: Giorgos Zirdelis
In these lectures we study the communication complexity of some problems on groups. We give the definition of a protocol when two parties are involved and generalize later to more parties.
Definition 1. A 2-party c-bit deterministic communication protocol is a depth-c binary tree such that:
- the leaves are the output of the protocol
- each internal node is labeled with a party and a function from that party’s input space to
Computation is done by following a path on edges, corresponding to outputs of functions at the nodes.
A public-coin randomized protocol is a distribution on deterministic protocols.
2 2-party communication protocols
We start with a simple protocol for the following problem.
Let be a group. Alice gets
and Bob gets
and their goal is to check if
, or equivalently if
.
There is a simple deterministic protocol in which Alice simply sends her input to Bob who checks if . This requires
communication complexity.
We give a randomized protocol that does better in terms on communication complexity. Alice picks a random hash function . We can think that both Alice and Bob share some common randomness and thus they can agree on a common hash function to use in the protocol. Next, Alice sends
to Bob, who then checks if
.
For we get constant error and constant communication.
3 3-party communication protocols
There are two ways to extend 2-party communication protocols to more parties. We first focus on the Number-in-hand (NIH), where Alice gets , Bob gets
, Charlie gets
, and they want to check if
. In the NIH setting the communication depends on the group
.
3.1 A randomized protocol for the hypercube
Let with addition modulo 2. We want to test if
. First, we pick a linear hash function
, i.e. satisfying
. For a uniformly random
set
. Then,
- Alice sends
- Bob send
- Charlie accepts if and only if
The hash function outputs 1 bit. The error probability is and the communication is
. For a better error, we can repeat.
3.2 A randomized protocol for 
Let where
. Again, we want to test if
. For this group, there is no 100% linear hash function but there are almost linear hash function families
that satisfy the following properties:
we have
we have
Assuming some random hash function (from a family) that satisfies the above properties the protocol works similar to the previous one.
- Alice sends
- Bob sends
- Charlie accepts if and only if
We can set to achieve constant communication and constant error.
Analysis
To prove correctness of the protocol, first note that , then consider the following two cases:
- if
then
- if
then
It now remains to show that such hash function families exist.
Let be a random odd number modulo
. Define
where the product is integer multiplication. In other words we output the bits
of the integer product
.
We now verify that the above hash function family satisfies the three properties we required above.
Property (3) is trivially satisfied.
For property (1) we have the following. Let and
and
. The bottom line is how
compares with
. In more detail we have that,
Notice, that if in the addition the carry into the
bit is
, then
otherwise
which concludes the proof for property (1).
Finally, we prove property (2). We start by writing where
is odd. Bitwise, this looks like
.
The product for a uniformly random
, bitwise looks like
. We consider the two following cases for the product
:
- If
, or equivalently
, the output never lands in the bad set
(some thought should be given to the representation of negative numbers – we ignore that for simplicity).
- Otherwise, the hash function output has
uniform bits. Again for simplicity, let
. Thus,
In other words, the probability of landing in any small set is small.
4 Other groups
What happens in other groups? Do we have an almost linear hash function for matrices? The answer is negative. For
and
the problem of testing equality with
is hard.
We would like to rule out randomized protocols, but it is hard to reason about them directly. Instead, we are going to rule out deterministic protocols on random inputs. For concreteness our main focus will be .
First, for any group element we define the distribution on triples,
, where
are uniformly random elements. Note the product of the elements in
is always
.
Towards a contradiction, suppose we have a randomized protocol for the
problem. In particular, we have
This implies a deterministic protocol with the same gap, by fixing the randomness.
We reach a contradiction by showing that for every deterministic protocols using little communication (will quantify later), we have
We start with the following lemma, which describes a protocol using product sets.
Lemma 1. (The set of accepted inputs of) A deterministic -bit protocol can be written as a disjoint union of
“rectangles,” that is sets of the form
.
Proof. (sketch) For every communication transcript , let
be the set of inputs giving transcript
. The sets
are disjoint since an input gives only one transcript, and their number is
, i.e. one for each communication transcript of the protocol. The rectangle property can be proven by induction on the protocol tree.
Next, we show that these product sets cannot distinguish these two distributions , and for that we will use the pseudorandom properties of the group
.
Lemma 2. For all and we have
Recall the parameter from the previous lectures and that when the group
is
then
.
Proof. Pick any and let
be the inputs of Alice, Bob, and Charlie respectively. Then
If either or
is small, that is
or
, then also
because the term
will be small. We will choose
later.
Otherwise, and
are large, which implies that
and
are uniform over at least
elements. Recall from Lecture 9 that this implies
, where
is the uniform distribution.
By Cauchy–Schwarz we obtain,
The last inequality follows from the fact that .
This implies that and
, because taking inverses and multiplying by
does not change anything. These two last inequalities imply that,
and thus we get that,
To conclude, based on all the above we have that for all and independent of the choice of
, it is either the case that
or
and we will now choose the to balance these two cases and finish the proof:
The above proves that the distribution behaves like the uniform distribution for product sets, for all
.
Returning to arbitrary deterministic protocols , write
as a union of
disjoint rectangles by the first lemma. Applying the second lemma and summing over all rectangles we get that the distinguishing advantage of
is at most
. For
the advantage is at most
and thus we get a contradiction on the existence of such a correct protocol. We have concluded the proof of this theorem.
Theorem 3. Let be a group, and
be the minimum dimension of an irreducible representation of
. Consider the 3-party, number-in-hand communication protocol
where
. Its randomized communication complexity is
.
For the communication is
. This is tight up to constants, because Alice can send her entire group element.
For the group the known bounds on
yield communication
. This bound is tight for the problem of distinguishing
from
for
, as we show next. The identity element
for the group
is the identity permutation. If
then
is a permutation that maps some element
to
. The idea is that the parties just need to “follow”
, which is logarithmically smaller than
. Specifically, let
be the permutations that Alice, Bob and Charlie get. Alice sends
. Bob gets
and sends
to Charlie who checks if
. The communication is
. Because the size of the group is
, the communication is
.
This is also a proof that cannot be too large for
, i.e. is at most
.
5 More on 2-party protocols
We move to another setting where a clean answer can be given. Here we only have two parties. Alice gets , Bob gets
, and they want to know if
.
When is abelian, the elements can be reordered as to check whether
. This requires constant communication (using randomness) as we saw in Lecture 12, since it is equivalent to the check
where
and
.
We will prove the next theorem for non-abelian groups.
Theorem 1. For every non-abelian group the communication of deciding if
is
.
Proof. We reduce from unique disjointness, defined below. For the reduction we will need to encode the And of two bits as a group product. (This question is similar to a puzzle that asks how to hang a picture on the wall with two nails, such that if either one of the nails is removed, the picture will fall. This is like computing the And function on two bits, where both bits (nails) have to be 1 in order for the function to be 1.) Since
is non-abelian, there exist
such that
, and in particular
with
. We can use this fact to encode And as
In the disjointness problem Alice and Bob get inputs respectively, and they wish to check if there exists an
such that
. If you think of them as characteristic vectors of sets, this problem is asking if the sets have a common element or not. The communication of this problem is
. Moreover, in the variant of this problem where the number of such
’s is 0 or 1 (i.e. unique), the same lower bound
still applies. This is like giving Alice and Bob two sets that either are disjoint or intersect in exactly one element, and they need to distinguish these two cases.
Next, we will reduce the above variant of the set disjointness to group products. For we product inputs for the group problem as follows:
Now, the product we originally wanted to compute becomes
If there isn’t an such that
, then each product term
is 1 for all
, and thus the whole product is 1.
Otherwise, there exists a unique such that
and thus the product will be
, with
being in the
-th position. If Alice and Bob can test if the above product is equal to 1, they can also solve the unique set disjointness problem, and thus the lower bound applies for the former.
We required the uniqueness property, because otherwise we might get a product that could be equal to 1 in some groups.