3
[2312.03076] XOR Lemmas for Communication via Marginal Information
source link: https://arxiv.org/abs/2312.03076
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
[Submitted on 5 Dec 2023]
XOR Lemmas for Communication via Marginal Information
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 Ω~(Cn−−√)-bit protocol has advantage exp(−Ω(n)) for computing the n-fold xor f⊕n. We prove exponentially small bounds in the average case setting, and near optimal bounds for product distributions and for bounded-round protocols.
| Subjects: | Computational Complexity (cs.CC) |
| Cite as: | arXiv:2312.03076 [cs.CC] |
| (or arXiv:2312.03076v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2312.03076 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK