Log-rank and lifting for AND-functions
Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is bounded by a polynomia...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2010.08994 http://arxiv.org/abs/2010.08994 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|