A Hierarchy for Constant Communication Complexity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911507654115328 |
|---|---|
| author | Ambainis, Andris Klauck, Hartmut Lim, Debbie |
| author_facet | Ambainis, Andris Klauck, Hartmut Lim, Debbie |
| contents | Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from previous attempts of this endeavor, we consider two communication complexity measures as equivalent, if, when one is constant, then the other is constant as well, and vice versa. Most previous considerations of similar topics have been using polylogarithmic input length as a defining characteristic of equivalence. In this paper, two measures ${\cal C}_1, {\cal C}_2$ are constant-equivalent, if and only if for all total Boolean (families of) functions $f:\{0, 1\}^n\times\{0, 1\}^n\rightarrow \{0, 1\}$ we have ${\cal C}_1(f)=O(1)$ if and only if ${\cal C}_2(f)=O(1)$. We identify five equivalence classes according to the above equivalence relation. Interestingly, the classification is counter-intuitive in that powerful models of communication are grouped with weak ones, and seemingly weaker models end up on the top of the hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22004 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Hierarchy for Constant Communication Complexity Ambainis, Andris Klauck, Hartmut Lim, Debbie Computational Complexity Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from previous attempts of this endeavor, we consider two communication complexity measures as equivalent, if, when one is constant, then the other is constant as well, and vice versa. Most previous considerations of similar topics have been using polylogarithmic input length as a defining characteristic of equivalence. In this paper, two measures ${\cal C}_1, {\cal C}_2$ are constant-equivalent, if and only if for all total Boolean (families of) functions $f:\{0, 1\}^n\times\{0, 1\}^n\rightarrow \{0, 1\}$ we have ${\cal C}_1(f)=O(1)$ if and only if ${\cal C}_2(f)=O(1)$. We identify five equivalence classes according to the above equivalence relation. Interestingly, the classification is counter-intuitive in that powerful models of communication are grouped with weak ones, and seemingly weaker models end up on the top of the hierarchy. |
| title | A Hierarchy for Constant Communication Complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2509.22004 |