Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-194 | 5th December 2023 00:27

XOR Lemmas for Communication via Marginal Information

RSS-Feed




TR23-194
Authors: Siddharth Iyer, Anup Rao
Publication: 5th December 2023 00:28
Downloads: 204
Keywords: 


Abstract:

We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every $C$-bit protocol has bounded advantage for computing a Boolean function $f$, then every $\tilde \Omega(C \sqrt{n})$-bit protocol has advantage $\exp(-\Omega(n))$ for computing the $n$-fold xor $f^{\oplus n}$. We prove exponentially small bounds in the average case setting, and near optimal bounds for product distributions and for bounded-round protocols.



ISSN 1433-8092 | Imprint