TY - GEN
T1 - Strong XOR Lemma for Information Complexity
AU - Sawettamalya, Pachara
AU - Yu, Huacheng
N1 - Publisher Copyright:
© 2025 Owner/Author.
PY - 2025/6/15
Y1 - 2025/6/15
N2 - For any {0,1}-valued function f, its n-folded XOR is the function fλ• n where fλ• n(X1, ..., Xn) = f(X1) λ• λ¯ λ• f(Xn). Given a procedure for computing the function f, one can apply a "naive"approach to compute fλ• n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n-1) requires revealing I bits of information about the players' inputs, then computing fλ• n with a constant error requires revealing ω(n) · (I - 1 - on(1)) bits of information about the players' inputs. Our result demonstrates that the naive protocol for computing fλ• n is both information-theoretically optimal and asymptotically tight in error trade-offs.
AB - For any {0,1}-valued function f, its n-folded XOR is the function fλ• n where fλ• n(X1, ..., Xn) = f(X1) λ• λ¯ λ• f(Xn). Given a procedure for computing the function f, one can apply a "naive"approach to compute fλ• n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n-1) requires revealing I bits of information about the players' inputs, then computing fλ• n with a constant error requires revealing ω(n) · (I - 1 - on(1)) bits of information about the players' inputs. Our result demonstrates that the naive protocol for computing fλ• n is both information-theoretically optimal and asymptotically tight in error trade-offs.
KW - Communication Complexity
KW - Information Complexity
KW - XOR Lemma
UR - https://www.scopus.com/pages/publications/105009813350
UR - https://www.scopus.com/pages/publications/105009813350#tab=citedBy
U2 - 10.1145/3717823.3718258
DO - 10.1145/3717823.3718258
M3 - Conference contribution
AN - SCOPUS:105009813350
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1626
EP - 1637
BT - STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing
A2 - Koucky, Michal
A2 - Bansal, Nikhil
PB - Association for Computing Machinery
T2 - 57th Annual ACM Symposium on Theory of Computing, STOC 2025
Y2 - 23 June 2025 through 27 June 2025
ER -