2010/04/16 by C. Palazuelos, Carlos Palazuelos, David Pérez-Garcı́a +6
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1004.2882
arxiv created 2010/04/16 · openalex publication_date 2010/04/16 · arxiv updated 2010/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.