XOR Lemmas for Communication via Marginal Information
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913412654563328 |
|---|---|
| author | Iyer, Siddharth Rao, Anup |
| author_facet | Iyer, Siddharth Rao, Anup |
| contents | We define the $\textit{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 Ω(C \sqrt{n})$-bit protocol has advantage $\exp(-Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03076 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | XOR Lemmas for Communication via Marginal Information Iyer, Siddharth Rao, Anup Computational Complexity We define the $\textit{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 Ω(C \sqrt{n})$-bit protocol has advantage $\exp(-Ω(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. |
| title | XOR Lemmas for Communication via Marginal Information |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2312.03076 |