3
$\begingroup$

In the book Computational Complexity (By Sanjeev Arora and Boaz Barak) a method called "The fooling set" is mentioned, when trying to bound the communication complexity of a function from below. A google search brough up the relevant chapter online. If you have the book, it is on part 13.2.1

There is a term called "communication pattern" in that chapter that I fail to completely understand. The following explains why.

The fooling set method is used to show that the Equality function $EQ(x,y)$ (on two arguments of $n$ bits) has a communication complexity of at least $n$. First, if for some protocol arguments of $(x,x)$ and arguments of $(x',x')$ yield the same "communication pattern" between the two players, we can conclude that arguments of $(x,x')$ and $(x',x)$ will also yield that exact same "communication pattern" between the two players.

Next, we assume that some protocol exists whose complexity is at most $n-1$ bits. Therefore there are at most $2^{n-1}$ possible "communication patterns"$^{(***)}$. However, there are $2^n$ different choices for argument pairs of the form $(x,x)$. By the pigeonhole principle, there must be two pairs of arguments $(x,x)$ and $(x',x')$ for which the produced "communication pattern" between the two players is exactly the same. By the previous arguments we expect that $(x,x)$ and $(x,x')$ will yield the same "communication pattern" between the two players, which means that $EQ(x,x) = EQ(x,x')$ which is a contradiction.

It seems like "communication pattern" means two different things in those two arguments. By the first argument I conclude that two "communication patterns" are equal if the messages that player 1 has sent in the first invocation of the protocol equal to the messages he has sent in the second invocation. The same goes for player 2.

The second argument claims that there are only $2^{n-1}$ possible communication patterns for a protocol with communication complexity of $n-1$ bits. By this I conclude that two communication patterns are the same if list of bits sent on the wire are the same, disregarding who sent each bit.

For example, if I try to apply the idea of "communication complexity" from the second argument to the first one, I get the following:

If the arguments $(x,x)$ and $(x',x')$ yield the same "communication complexity", but the messages sent by player 1 in the case of $(x,x)$ are not the same as in the case of $(x',x')$ then it is not necessarily true that $(x,x')$ yield that same "communication pattern".

I appreciate any ideas about this, and I'm looking forward to read the next pages of the book :)

$\endgroup$
1
$\begingroup$

Good thinking. The answer lies in the definition of a communication protocol on p. $192$. The definition says that it's determined by the communication protocol which player communicates next, depending only on the communication pattern of the previous rounds and not on the players' inputs. So the idea is that the players communicate one bit at a time, and they both have to know and agree who's going to send the next bit, so they can base that decision only on their common knowledge and not on their private inputs. Since the identities of the communicating players are fully determined by the $2^n$ choices of bits, they don't add to those choices.

One model in which your idea would apply is if a player can choose not to transmit a bit, thereby prompting the other player to transmit one. This is covered in the remark at the bottom of p. $192$.

$\endgroup$
  • $\begingroup$ You won't believe it, but my copy of this book has a different definition than the one I included on the link. I just saw it now. In my copy every player can send any amount of bits he wants in each turn, and the data sent depends on the inputs too. My copy is from 2009, I wonder if the one on the link is a newer version. Thank you! $\endgroup$ – real Sep 11 '15 at 7:26
  • $\begingroup$ @real: I do believe it. People make mistakes, and a good number of questions on this site are about things that people don't understand in books and it turns out the books were wrong. $\endgroup$ – joriki Sep 11 '15 at 7:29
  • $\begingroup$ @real: You write "and the data sent depends on the inputs too". That's still the case here, the data sent has to depend on the inputs. The question is whether the number of bits sent can depend on the inputs or must be determined by the public knowledge. $\endgroup$ – joriki Sep 11 '15 at 7:30
  • $\begingroup$ The definition in my copy is that there is just one type of function, $P_i : {\{0,1\}}^* \rightarrow {\{0,1\}}^*$, where $p_i := P_i(x,p_1,p_2,...,p_{i-1})$. With this definition the proof would be incorrect: The amount of "communication patterns" of complexity n-1 bits would be more than $2^{n-1}$, because we lack the information about who sent each bit. $\endgroup$ – real Sep 11 '15 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.