Partition bound is quadratically tight for product distributions
Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $μ$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $$\mathsf{CC}^μ_{0.49}(f) = O\left(\left(\log \mathsf{prt}_{1/8}(f) \cdot \log \log \mathsf{prt}_{1/8}(f)\right)^2\right),$$ where $\mathsf...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/1512.01968 http://arxiv.org/abs/1512.01968 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|