TY - GEN

T1 - Strong XOR Lemma for Communication with Bounded Rounds

T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022

AU - Yu, Huacheng

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function f:X×Y?{0,1}, the n-fold XOR function f?n: Xn× Yn ? {0,1} maps n input pairs (X1,. . . , Xn, Y1,. . ., Yn) to the XOR of the n output bits f(X1, Y1)?. . .? f(Xn, Yn). We prove that if every r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes f? n with probability 1/2+exp(-O(n)) must use n (r-O(r) C-1) bits. When r is a constant and C is sufficiently large, this is O(n C) bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits f(Xi, Yi) independently and outputs their XOR, up to a constant factor in n. A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [17]. By the equivalence between the discrepancy and the correlation with 2-bit communication protocols [19], our new XOR lemma implies the previous result.

AB - In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function f:X×Y?{0,1}, the n-fold XOR function f?n: Xn× Yn ? {0,1} maps n input pairs (X1,. . . , Xn, Y1,. . ., Yn) to the XOR of the n output bits f(X1, Y1)?. . .? f(Xn, Yn). We prove that if every r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes f? n with probability 1/2+exp(-O(n)) must use n (r-O(r) C-1) bits. When r is a constant and C is sufficiently large, this is O(n C) bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits f(Xi, Yi) independently and outputs their XOR, up to a constant factor in n. A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [17]. By the equivalence between the discrepancy and the correlation with 2-bit communication protocols [19], our new XOR lemma implies the previous result.

KW - communication complexity

KW - xor lemma

UR - http://www.scopus.com/inward/record.url?scp=85146358643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85146358643&partnerID=8YFLogxK

U2 - 10.1109/FOCS54457.2022.00114

DO - 10.1109/FOCS54457.2022.00114

M3 - Conference contribution

AN - SCOPUS:85146358643

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 1186

EP - 1192

BT - Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

PB - IEEE Computer Society

Y2 - 31 October 2022 through 3 November 2022

ER -