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.
To prove correctness of the protocol, first note that , then consider the following two cases:
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
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 .
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
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.