The communication complexity of XOR games via summing operators

Details The communication complexity of XOR games via summing operators The communication complexity of XOR games via summing operators

2010-04-16

arxiv.org/abs/1004.2882v1

Computer Science

Computational Complexity

Scientific paper

The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to give good bounds, because the increment of the value of the game is linear (rather than exponential) in the number of communicated bits. We show in this paper the existence of XOR games where the discrepancy method yields bounds as poor as one desires. Indeed, we show the existence of such games with any previously prescribed value. To prove this result we apply the theory of p-summing operators, a central topic in Banach space theory. We show in the paper other applications of this theory to the study of the communication complexity of XOR games.

Affiliated with

Also associated with

No associations

Rating

The communication complexity of XOR games via summing operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The communication complexity of XOR games via summing operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The communication complexity of XOR games via summing operators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624428